86. 分隔链表

题目大意：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 由于 相对位置不能发生变化，所以不能用类似冒泡排序的思想。
你应当 保留 两个分区中每个节点的初始相对位置。

  • 题目意思就是让你用两个链表存,第一个存<target的结点,
  • 第二个存>=target的结点,最后再把第二个链表拼到第一个链表最后.

image.png
复杂度分析

  • 时间复杂度: O(n)，其中 n 是原链表的长度。我们对该链表进行了一次遍历。

  • 空间复杂度: O(1)。

    1. //[1,4,3,2,5,2]->[1,2,2,4,3,5]
    2. //虚拟节点法，考察画图能力？抽象思维转换具体思路
    3. func partition(head *ListNode, x int) *ListNode {
    4.   Small_Head ,Large_Head := &ListNode{}, &ListNode{}  
    5.   Small_Tail := Small_Head
    6.   Large_Tail := Large_Head    //1，创建两个哑结点链表，头尾初始都是空
    8.   for head != nil {           //2，比较大小，把比x小的放前面
    9.       if head.Val < x {
    10.           Small_Tail.Next = head 
    11.           Small_Tail = Small_Tail.Next
    12.       } else {                //3，把比x大的不动【4，3，5，6】
    13.           Large_Tail.Next = head
    14.           Large_Tail = Large_Tail.Next
    15.       }
    16.       head = head.Next        //原链表不断前进至尾
    17.   } 
    18.   Large_Tail.Next = nil       //4，让源链表的尾指向空，防止成环【6 -> 1,2】
    19.   Small_Tail.Next = Large_Head.Next   //5,合并链表 小>点>大，新链表为从small哑结点下一跳开始
    21.   return Small_Head.Next
    22. }
    //简化代码版本，更易理解
func partition(head *ListNode, x int) *ListNode {
  dummy1, dummy2 := &ListNode{}, &ListNode{}
  pre1, pre2 := dummy1, dummy2                    //1，创两个空链表

  for head != nil {
      if head.Val < x {                       //2，扫描原表，＜x的放前面
          pre1.Next = head                    //难点，因为没有前置节点，所以把head当作头结点
          pre1 = pre1.Next                    //两个步骤：建头结点；头结点前进    

      } else {
          pre2.Next = head
          pre2 = pre2.Next
      }

      head = head.Next
  }

  pre2.Next = nil                             //大的链表尾巴置零，防止成环; 也把指向head的变为0
  pre1.Next = dummy2.Next                     //合并链表，小链表接在大链表后面

  return dummy1.Next
}