[LeetCode63]Partition List-CSDN博客

本文链接：https://blog.csdn.net/sbitswc/article/details/27282193

本文介绍了一种链表分隔算法，该算法可以将链表中小于特定值x的所有节点放置在大于等于x的节点之前，同时保持原有的相对顺序不变。通过两个遍历指针实现元素的有效插入和移动。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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.

Analysis:

The idea is stright forward

First, find the first element that is greater than or equal to x, pointer p2 and its former pointer p1

Second, from p2 to scan the list, if the element is less than x, insert it into the p1

Java

public ListNode partition(ListNode head, int x) {
        if(head==null || head.next == null) return head;
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode p1 = newHead;
        ListNode p2 = head;
        while(p2!=null&& p2.val<x){
        	p2 = p2.next;
        	p1 = p1.next;
        }
        while(p2!=null){
        	if(p2.next!=null && p2.next.val<x){
        		ListNode temp = p1.next;
        		p1.next = p2.next;
        		p2.next = p2.next.next;
        		p1.next.next = temp;
        		p1 = p1.next;
        	}
        	p2 = p2.next;
        }
        return newHead.next;
    }

c++

ListNode *partition(ListNode *head, int x) {
        ListNode *p = new ListNode(x-1);
        p->next = head;
        head = p;
        ListNode *pre;
        while(p!=NULL && p->val<x){// find the first element bigger than x
            pre = p;
            p = p->next;
        }
        if(p!=NULL){
            ListNode *cur = pre;// keep the start point
            while(p!=NULL){//scan later element to insert before start point
                if(p->val <x){
                    ListNode *temp = cur->next;
                    pre->next = p->next;
                    cur->next = p;
                    cur = p;
                    p->next = temp;
                    p = pre;
                }//if bigger move next
                pre = p;
                p = p->next;
            }
        }
        ListNode *temp = head;
        head = head->next;
        delete temp;
        return head;
        
    }