题解 | #划分链表#

题目描述
给出一个链表和一个值 ，以x为参照将链表划分成两部分，使所有小于x的节点都位于大于或等于x的节点之前。
两个部分之内的节点之间要保持的原始相对顺序。
例如：
给出 1→4→3→2→5→2和x=3,
返回 1→2→2→4→3→5.

方法一：暴力求解

求解思路
对于题目所要求，将小于x的节点放到大于等于x节点的左端，并且保持原来的相对位置，因此我们直接暴力解法，将小于x的节点直接移到前面，并且大于等于x的节点移到后面，直接上循环即可。

解题代码

import java.util.*;//参考De梦代码写出
public class Solution {
    public ListNode partition (ListNode head, int x) {
        ListNode left = new ListNode(0);//创建结点，left表示最后链表中的小端
        ListNode leftHead = left;
        ListNode right = new ListNode(0);//right表示最后链表中的大端
        ListNode rightHead = right;
        while(head!=null)
        {
            if(head.val<x)
            {
                left.next = head;
                left = left.next;
            }else
            {
                right.next = head;
                right =right.next;
            }
            head = head.next;
        }
        right.next = null;
        left.next = rightHead.next;
        return leftHead.next;
    }
}

复杂度分析
时间复杂度：一个while循环，O(N)
空间复杂度：对于链表，没有引入额外的空间，O(1)

方法二：双指针的思想

求解思路
双指针的想法，left指针从前面往后面跑，right指针从后面往前面跑，然后right指针找到小于x的节点，进行往前插入的操作，然后当right和left碰头时结束循环。（多理解！）

解题代码

import java.util.*;
public class Solution {
    public ListNode partition (ListNode head, int x) {
         ListNode leftPtr = new ListNode(0);
        leftPtr.next = head;
        ListNode dummyHead = leftPtr;//辅助节点，用于输出结果
        while(leftPtr.next!=null && leftPtr.next.val < x)
        {
            leftPtr = leftPtr.next;
        }
        //插入点的next
        ListNode nextPtr = leftPtr.next;
        //右指针，寻找需要前移的结点
        ListNode rightPtr = nextPtr;
        while(rightPtr!=null && rightPtr.next!=null){
            //找到需要前移的结点，执行插入操作
            if(rightPtr.next.val < x){
                leftPtr.next = rightPtr.next;
                rightPtr.next = rightPtr.next.next;
                leftPtr.next.next = nextPtr;
                leftPtr = leftPtr.next;
            }else
            {
                //右指针继续寻找
                rightPtr = rightPtr.next;
            }
        }
        return dummyHead.next;//返回结果
    }
}

复杂度分析
时间复杂度：一个while循环，O(N)。（同第一种方法）
空间复杂度：对于链表，没有引入额外的空间，O(1)