Reverse Linked List II

Question

Problem Statement

Reverse a linked list from position m to n.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return
1->4->3->2->5->NULL.

Note

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Challenge

Reverse it in-place and in one-pass

题解

此题在上题的基础上加了位置要求，只翻转指定区域的链表。由于链表头节点不确定，祭出我们的dummy杀器。此题边界条件处理特别tricky，需要特别注意。

  1. 由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点
  2. 找到第m个节点，使用for循环n-m次，使用上题中的链表翻转方法
  3. 处理第m-1个和第n+1个节点
  4. 返回dummy->next

C++

  1. /**
  2.  * Definition of singly-linked-list:
  3.  *
  4.  * class ListNode {
  5.  * public:
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode(int val) {
  9.  *        this->val = val;
  10.  *        this->next = NULL;
  11.  *     }
  12.  * }
  13.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param head: The head of linked list.
  18.      * @param m: The start position need to reverse.
  19.      * @param n: The end position need to reverse.
  20.      * @return: The new head of partial reversed linked list.
  21.      */
  22.     ListNode *reverseBetween(ListNode *head, int m, int n) {
  23.         if (head == NULL || m > n) {
  24.             return NULL;
  25.         }
  27.         ListNode *dummy = new ListNode(0);
  28.         dummy->next = head;
  29.         ListNode *node = dummy;
  31.         for (int i = 1; i != m; ++i) {
  32.             if (node == NULL) {
  33.                 return NULL;
  34.             } else {
  35.                 node = node->next;
  36.             }
  37.         }
  39.         ListNode *premNode = node;
  40.         ListNode *mNode = node->next;
  41.         ListNode *nNode = mNode, *postnNode = nNode->next;
  42.         for (int i = m; i != n; ++i) {
  43.             if (postnNode == NULL) {
  44.                 return NULL;
  45.             }
  47.             ListNode *temp = postnNode->next;
  48.             postnNode->next = nNode;
  49.             nNode = postnNode;
  50.             postnNode = temp;
  51.         }
  52.         premNode->next = nNode;
  53.         mNode->next = postnNode;
  55.         return dummy->next;
  56.     }
  57. };

Java

  1. /**
  2.  * Definition for ListNode
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     /**
  14.      * @param ListNode head is the head of the linked list 
  15.      * @oaram m and n
  16.      * @return: The head of the reversed ListNode
  17.      */
  18.     public ListNode reverseBetween(ListNode head, int m , int n) {
  19.         ListNode dummy = new ListNode(0);
  20.         dummy.next = head;
  22.         // find the mth node
  23.         ListNode premNode = dummy;
  24.         for (int i = 1; i < m; i++) {
  25.             premNode = premNode.next;
  26.         }
  28.         // reverse node between m and n
  29.         ListNode prev = null, curr = premNode.next;
  30.         while (curr != null && (m <= n)) {
  31.             ListNode nextNode = curr.next;
  32.             curr.next = prev;
  33.             prev = curr;
  34.             curr = nextNode;
  35.             m++;
  36.         }
  38.         // join head and tail before m and after n
  39.         premNode.next.next = curr;
  40.         premNode.next = prev;
  42.         return dummy.next;
  43.     }
  44. }

源码分析

  1. 处理异常
  2. 使用dummy辅助节点
  3. 找到premNode——m节点之前的一个节点
  4. 以nNode和postnNode进行遍历翻转，注意考虑在遍历到n之前postnNode可能为空
  5. 连接premNode和nNode，premNode->next = nNode;
  6. 连接mNode和postnNode，mNode->next = postnNode;

务必注意node 和node->next的区别！！，node指代节点，而node->next指代节点的下一连接。