LeetCode 86 Partition List

阅读数: 113次 2019-03-20

Description

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.

Example

1 2	Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5

Analysis

Solution #1

利用双指针，一个指针target指向要交换节点的前一个节点，即下一个节点值大于给定值的节点。

问题在于如何交换第一个小于x的节点到target后。

之后从该节点开始向后遍历到后继节点小于给定值的节点，记为cur。标记cur.next.next为next节点，target.next为node节点，这样就有四个指针:

之后令target的后继指向cur的后继

target指向target的后继

target的后继指向node

cur的后继指向next即可

最后恢复的节点顺序如下

target和node不变，cur继续向后遍历即可。

代码：

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode target = dummy;
        
        while (target.next != null && target.next.val < x) {
            target = target.next;
        }
        ListNode cur = target;
        while (cur.next != null) {
            if (cur.next.val < x) {
                ListNode node = target.next;//缓存target.next节点
                ListNode next = cur.next.next;//缓存cur.next.next节点
                target.next = cur.next;
                target = target.next;
                target.next = node;
                cur.next = next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

Solution #2

利用新开两个哑结点，遍历原链表，当正在遍历的节点值小于x的时候就连接到第一个链表节点上，并清除该节点的后继（实际上就相当于复制了一个相同值的全新节点），如果大于等于x就连接到第二个链表上，最后将第一个链表的尾部连接上第二个链表的头部。

该方法实际属于复制新节点，在我看来有投机取巧的成分在（笑)

代码：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(0);
        ListNode dummyHead2 = new ListNode(0);
        ListNode node1 = dummyHead1;
        ListNode node2 = dummyHead2;
        while (head != null) {
            if (head.val < x) {
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }
        node1.next = dummyHead2.next;
        return dummyHead1.next;
    }
}

本文作者： Dominic
本文链接： https://dominicpoi.com/2019/03/20/LeetCode-86-Partition-List/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！