程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Partition List

leetcode筆記:Partition List

編輯:關於C++

一. 題目描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

二. 題目分析

題目的大意是,給定一個單鏈表和一個值x,把鏈表中小於x的放到x的前面,大於等於x的放到x的後面,每部分元素的原始相對位置不變。

該題是一個普通的鏈表遍歷的題目,需要注意的地方在於必須將鏈表的最後一個節點的下一個節點更新為null,不然鏈表會出現環,從而導致死循環的情況。

三. 示例代碼

#include 

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        ListNode *LessHeader = new ListNode(10);
        ListNode *LessTail = LessHeader;

        ListNode *GreaterHeader = new ListNode(10);
        ListNode *GreaterTail = GreaterHeader;

        while(head != NULL)
        {
            if (head->val < x)
            {
                LessTail->next = head;
                LessTail = head;
            }
            else
            {
                GreaterTail->next = head;
                GreaterTail = head;
            }

            head = head->next;
        }

        LessTail->next = GreaterHeader->next;
        GreaterTail->next = NULL;
        delete GreaterHeader;

        head = LessHeader->next;
        delete LessHeader;

        return head;
    }
};

四. 小結

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved