92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

Solution：

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
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    int chang_len = n-m+1;//逆置的结点个数。
    struct ListNode* prevHead = NULL;//记录开始逆置结点的前驱。
    struct ListNode* result = head;//用于最后返回。
    while(head && --m){ //到达开始逆置的位置。
        prevHead = head;
        head = head->next;
    }
    
    struct ListNode * modify_list_tail = head;//将该结点之前当前开始逆置的结点。
    struct ListNode * newHead = NULL;//用于逆置结点。
    while(head && chang_len){
        struct ListNode * next = head->next;
        head->next = newHead;
        newHead = head;
        head = next;
        chang_len--;
    }
    //此时head就到了n处，modify_list_tail就到了逆置段的最后一个结点。
    //将modify_list_tail 与 head连接。
    modify_list_tail->next = head;
    
    if(prevHead){ //如果prevHead不为空，说明不是从第一个几点开始逆置的。 m > 1。
        prevHead->next = newHead;
    }else{
        result = newHead; //如果prevHead为空， 则说明是从第一个就开始逆置，直接将逆置后的头结点赋值给res，m=1。
    }
    return result;
}

思路：

解决这个问题主要是要找关键节点。

这个题的关键节点为：

  • 要逆置的结点的前一个结点（prevHead）。
  • 要逆置的第一个结点。（直接用head来探测）。
  • 要逆置的最后一个结点。（此结点为逆置前的第一个结点，逆置后就变为了最后一个结点）
  • 要逆置的最后一个结点的后一个结点。（在用head逆置后，head就到了逆置后的这个结点。）
  1. 找到前两个结点。
  2. 从m开始，到n，一共需要n-m+1个结点需要逆置。所以要逆置n-m+1次。
  3. 将逆置后的尾结点 与 逆置段后面一个结点相连。
  4. 如果结点是从开始逆置，将逆置后的头结点返回。否则，将前面的结点与逆置后的头结点链接返回。