反转链表专项学习记录

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func reverseList(head *ListNode) *ListNode {
  var pre *ListNode  // 需要注意，不要写成 pre := *ListNode{}，这样就完成了初始化、值不是 nil 了
  cur := head
  
  for cur != nil {
    next := cur.Next // 保存 next，防止丢失
    cur.Next = pre   // 断 cur 尾，使其指向反转链表头部
    pre = cur        // 更新 pre，让其移动到 cur 的位置，此时 cur 成为新头部，pre 符合其定义仍然指向反转链表的头部
    cur = next       // cur 移动，指向下一个待反转节点
  }
  
  return pre
}

1
2
3
4

next := cur.Next
cur.Next = pre
pre = cur
cur = next

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func reverseBetween(head *ListNode, left int, right int) *ListNode {
  // corner case
  if left == right || head.Next == nil {
    return head
  }
  
  dummy := &ListNode{Next: head} // 用 dummy 处理 left 为 1 的情况
  p0 := dummy
  for range left - 1 { 					 // 遍历到反转链表的前一个节点，只需遍历这一次 
    p0 = p0.Next
  }
  
  pre := &ListNode{}
  cur := p0.Next
  for range right - left + 1 {
    // 这 4 句同之前
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
  }
  p0.Next.Next = cur // p0.Next 指向的是原先的第一个节点，而这第一个节点此时为反转链表的尾节点（头插法🐎）。所以此时需要让其与后半段正常链表连接，而此时的 cur 指向的就是后半段的头部，所以令其指向 cur
  p0.Next = pre      // p0.Next 为反转链表的尾部，此时也需要将前半段与反转链表连接。p0 是前半段的尾部、反转链表的前一个节点，所以令其 next 指向反转链表的头部，以完成前半段的连接
  
  return dummy.Next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func reverseKGroup(head *ListNode, k int) *ListNode {
	cntHead := head
	n := 0
	for cntHead != nil { // 这里计数是方便后续 K 个、K 个的遍历需求
		cntHead = cntHead.Next
		n++
	}
	
  // 这 4 步定义与 LC92 完全一致
	dummy := &ListNode{Next: head}
	p0 := dummy
	cur := p0.Next
	pre := &ListNode{}

  // 保证每次遍历够 K 个
	for ; n >= k; n -= k {
    // 对区间内链表进行 K 次反转操作
		for range k {
      // 这 4 步同前面的题，意思完全一致
			next := cur.Next
			cur.Next = pre
			pre = cur
			cur = next
		}
		
		reverseTail := p0.Next // 新增操作，保存本次循环的反转链表的尾节点
		p0.Next.Next = cur     
		p0.Next = pre          
		p0 = reverseTail       // 将 p0 更新为本次循环的反转链表的尾节点，为下一个循环作准备。对于下一个循环而言，p0 符合定义
	}

	return dummy.Next
}