LeetCode86. 分隔链表

我会带着你远行 2022-05-10 07:33 196阅读 0赞

给定一个链表和一个特定值 *x*，对链表进行分隔，使得所有小于 *x* 的节点都在大于或等于 *x* 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

**示例:**

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

--------------------

思路：双指针。

1.找到链表中pre结点（pre.val<x&&pre.next.val>=x）

2.遍历链表，将所有结点值<x的结点插入到pre结点之后，更新pre的位置。

![70][]

/**
     * 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||head.next==null){
                return head;
            }
            ListNode h=new ListNode(Integer.MIN_VALUE);
            h.next=head;
            ListNode res=h;
            ListNode pre;//目标结点（pre的值<x&&pre.next.val>=x）
            while(h.next!=null){  //寻找目标结点pre
                if(h.val<x&&h.next.val>=x){
                    break;
                }
                h=h.next;
            }
            int n=h.val;//用来判断链表头结点是否改变
            pre=h;
    
            //继续遍历链表，将结点值<x的结点放到pre结点之后，更新pre结点位置(pre=pre.next)
            while (h.next!=null){
                if(h.next.val<x){
                    ListNode t=h.next;
                    h.next=h.next.next;
                    ListNode tmp=pre.next;
                    pre.next=t;
                    t.next=tmp;
                    pre=pre.next;
                }else{
                    if(h.next==null){
                        break;
                    }
                    h=h.next;
                }
    
            }
    
            if(n==Integer.MIN_VALUE){//头结点改变的情况
                return res.next;
            }
            return head;//头结点不变的情况
        }
    }

[70]: /images/20220510/afea300c2fd544e4b3797f0fa895a6ec.png