题目

题解

代码

/** * Definition for singly-linked list. public class ListNode { int val; ListNode * next; ListNode(int x) { val = x; } } */

public class code86 {

    public static ListNode partition(ListNode head, int x) {
        ListNode before_head = new ListNode(0);// 哑结点 1
        ListNode before = before_head;
        ListNode after_head = new ListNode(0);// 哑结点 2
        ListNode after = after_head;

        while (head != null) { // 利用 head 指针遍历原链表
            if (head.val < x) { // 若 head 指针指向的元素值 小于 x，该节点应当是 "before" 链表的一部分
                before.next = head;
                before = before.next;
                head = head.next;
            } else if (head.val >= x) { // 若 head 指针指向的元素值 大于等于 x，该节点应当是 "after" 链表的一部分
                after.next = head;
                after = after.next;
                head = head.next;
            }
        }
        after.next = null; // "after" 链表的最后一个节点也将是重组链表的结束节点
        before.next = after_head.next; // 将 "before" 和 "after" 连接，组成所求的链表

        return before_head.next; // 返回重组链表的头结点
    }

    public static void print(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode current = node;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(2);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(2);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        print(listNode1);

        int x = 3;

        ListNode head = partition(listNode1, x);
        print(head);
    }
}
86. 分隔链表

题目

题解

代码

参考
