leetcode86. Partition List

layman 發布于2019-08-15 10:45 / 3340人閱讀

摘要：當前節點的前一個節點插入位置的前一個節點，以及記錄初始位置的節點。當發現一個需要交換的節點時，先獲得這個節點，然后將指向節點的后一個節點。最后將兩個鏈表連接。代碼相比于第一種更加清晰一些。

題目要求

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的值放在后面，移動的過程中不改變數字之間的相對順序。

思路一：移動節點

該思路需要我們記錄3個節點。當前節點的前一個節點currentPrev,插入位置的前一個節點prev，以及記錄初始位置的節點start。當發現一個需要交換的節點時，先獲得這個節點，然后將currentPrev指向節點的后一個節點。之后將當前的節點插入到prev之后。代碼如下：

    public ListNode partition(ListNode head, int x) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode start = new ListNode(0);
        ListNode prev = new ListNode(0);
        ListNode currentPrev = new ListNode(0);
        start.next = prev;
        prev.next = head;
        currentPrev.next = head;
        while(currentPrev.next!=null && currentPrev.next.val
思路二：使用兩個鏈表
我們設置兩個頭指針當做兩個鏈表，當遇到的數值小于x，則加入第一個鏈表，否則加入第二個鏈表。最后將兩個鏈表連接。代碼相比于第一種更加清晰一些。
    public ListNode partition2(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode curr = head, first = dummy1, second = dummy2;
        while (curr != null) {
            if (curr.val < x) {
                first.next = curr;
                first = first.next;
            } else {
                second.next = curr;
                second = second.next;
            }
            curr = curr.next;
        }
        first.next = dummy2.next;
        second.next = null;
        return dummy1.next;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Leetcod Partition LeetCode partition vs sharding

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67328.html

[LeetCode] 86. Partition List

Problem 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 ea...

Yuqi 2019-08-16 13:54 評論0 收藏0
[LeetCode] 763. Partition Labels

Problem A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers represe...

iliyaku 2019-08-16 13:58 評論0 收藏0
[LintCode/LeetCode] Partition List

摘要：新建兩個鏈表，分別存和的結點。令頭結點分別叫作和，對應的指針分別叫作和。然后遍歷，當小于的時候放入，否則放入。最后，讓較小值鏈表尾結點指向較大值鏈表頭結點，再讓較大值鏈表尾結點指向。 Problem Given a linked list and a value x, partition it such that all nodes less than x come before no...

崔曉明 2019-08-14 16:26 評論0 收藏0
[Leetcode] Palindrome Partitioning 回文分割

摘要：深度優先搜素復雜度時間空間思路因為我們要返回所有可能的分割組合，我們必須要檢查所有的可能性，一般來說這就要使用，由于要返回路徑，仍然是典型的做法遞歸時加入一個臨時列表，先加入元素，搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

leanote 2019-08-14 12:32 評論0 收藏0