1. 操作

以这道题为实例。

对链表的某一部分进行翻转时，需要记录以下这几个节点：

  • p0: 发生翻转区域的前置节点，这个是为了区域翻转后的连接（循环结束，p0.next为翻转后区间的最后一个元素）。为了统一处理（因为原链表有的翻转区域没有前置节点），先构造dummy=ListNode{next: head}。这样的话，翻转后的链表的头节点即为dummy.next。p0可能为dummy。
  • cur: 当前遍历到的节点，循环结束，cur为区域后的第一个元素
  • pre: 当前遍历到的节点的原链表中的上一个节点，在翻转后就是next。在最初翻转前为nullptr,循环结束，pre为翻转后的区域的第一个元素
  • nxt: 当前遍历到的节点的原链表中的下一个节点，下一个cur，在翻转后它的next就是pre。

操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
cur := p0.next
pre := nullptr
for cur in area; do
    nxt := cur.next
    cur.next = pre
    pre = cur
    cur = nxt
end loop
// one loop only change one "next"
// end loop, cur is next node for this area at the time
p0.next.next=cur // set next pointer of the reversed area's last node  
p0.next=pre // previous node's next pointer points to the first node

2. 例题

25.k个一组翻转链表

这个题的有一个关键：找到每一个翻转区间的p0。它实际就是上一个区间未翻转时的第一个节点。

go示例解法

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    cnt := 0
    for p:=head;p!=nil;p=p.Next{
        cnt++
    }
    dummy := &ListNode{0,head}
    p0 := dummy
    for ; cnt>=k ; cnt-=k {
        cur := p0.Next
        var pre *ListNode
        nextp := p0.Next
        for i:=0;i<k;i++{
            nxt := cur.Next
            cur.Next = pre
            pre = cur
            cur = nxt
        }
        p0.Next.Next=cur
        p0.Next = pre
        p0=nextp
    } 
    return dummy.Next
}