分割链表

编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例:

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode dummyNode1 = new ListNode(0);
        ListNode dummyNode2 = new ListNode(0);

        ListNode cur = head;

        ListNode node1 = dummyNode1;
        ListNode node2 = dummyNode2;

        while (cur != null) {
            ListNode nex = cur.next;            //当前节点的下一节点
            if (cur.val < x) {                  //小于x放到dummyNode1
                node1.next = cur;
                node1 = node1.next;
                node1.next = null;              //从原链表断开
            } else {                            //大于等于x放到dummyNode2
                node2.next = cur;
                node2 = node2.next;
                node2.next = null;              //从原链表断开
            }
            cur = nex;
        }

        node1.next = dummyNode2.next;

        return dummyNode1.next;
    }
}

赏

谢谢你请我吃糖果

微信