左神算法学习笔记 - 012【入门】链表入门题目-划分链表

【算法讲解012【入门】链表入门题目-划分链表】 https://www.bilibili.com/video/BV1SV4y1i76r/?share_source=copy_web&vd_source=939a5033dc1ec4f712d59a4a4042e169

继续一道经典的链表题目，分隔链表。

题目的要求是，给定一个链表和一个值，然后把整个链表按照 < 整个值和 > 这个值进行划分，使得链表左侧是小于这个值的区域，链表右侧是大于这个值的区域。

这个题与「合并两个有序链表」以及「链表相加」的题目一样，都有使用虚拟头节点和不使用两种写法，个人认为使用头节点的版本相对好写一点：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(101);
        ListNode dummy2 = new ListNode(101);

        ListNode p1 = dummy1, p2 = dummy2;
        ListNode p = head;

        while (p != null) {
            if (p.val < x) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }

            p = p.next;
        }

        p1.next = dummy2.next;
        p2.next = null; // 这一步是避免最后的链表有环，也就是把右侧的末尾断开即可

        return dummy1.next;
    }
}

左神的版本依旧不推荐使用头节点：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode leftHead = null, leftTail = null;
        ListNode rightHead = null, rightTail = null;
        ListNode next = null;
        
        while (head != null) {
            next = head.next;
            head.next = null;

            if (head.val < x) {
                if (leftHead == null) {
                    leftHead = head;
                } else {
                    leftTail.next = head;
                }
                leftTail = head;
            } else {
                if (rightHead == null) {
                    rightHead = head;
                } else {
                    rightTail.next = head;
                }
                rightTail = head;
            }
            head = next;
        }

        if (leftHead == null) {
            return rightHead;
        }

        leftTail.next = rightHead;

        return leftHead;
    }
}

• 记住关键点是「小头小尾，大头大尾 + 一个 next 指针」五个变量

• 然后 head 在链表上遍历

• 比用头节点麻烦的一点是，需要针对小链表和大链表的 head 一开始为空的情况，做一个判空处理

• 最后还需要判断一下左边链表有没有，没有就返回右头，有就左连右，返回左头