Question

Source

• leetcode: Reverse Linked List II | LeetCode OJ
• lintcode: (36) Reverse Linked List II

Problem

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++

/**
 * Definition of singly-linked-list:
 *
 * class ListNode {
 * public:
 *   int val;
 *   ListNode *next;
 *   ListNode(int val) {
 *    this->val = val;
 *    this->next = NULL;
 *   }
 * }
 */
class Solution {
public:
  /**
   * @param head: The head of linked list.
   * @param m: The start position need to reverse.
   * @param n: The end position need to reverse.
   * @return: The new head of partial reversed linked list.
   */
  ListNode *reverseBetween(ListNode *head, int m, int n) {
    if (head == NULL || m > n) {
      return NULL;
    }

    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *node = dummy;

    for (int i = 1; i != m; ++i) {
      if (node == NULL) {
        return NULL;
      } else {
        node = node->next;
      }
    }

    ListNode *premNode = node;
    ListNode *mNode = node->next;
    ListNode *nNode = mNode, *postnNode = nNode->next;
    for (int i = m; i != n; ++i) {
      if (postnNode == NULL) {
        return NULL;
      }

      ListNode *temp = postnNode->next;
      postnNode->next = nNode;
      nNode = postnNode;
      postnNode = temp;
    }
    premNode->next = nNode;
    mNode->next = postnNode;

    return dummy->next;
  }
};

Java

/**
 * Definition for ListNode
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode(int x) {
 *     val = x;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  /**
   * @param ListNode head is the head of the linked list 
   * @oaram m and n
   * @return: The head of the reversed ListNode
   */
  public ListNode reverseBetween(ListNode head, int m , int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // find the mth node
    ListNode premNode = dummy;
    for (int i = 1; i < m; i++) {
      premNode = premNode.next;
    }

    // reverse node between m and n
    ListNode prev = null, curr = premNode.next;
    while (curr != null && (m <= n)) {
      ListNode nextNode = curr.next;
      curr.next = prev;
      prev = curr;
      curr = nextNode;
      m++;
    }

    // join head and tail before m and after n
    premNode.next.next = curr;
    premNode.next = prev;

    return dummy.next;
  }
}

源码分析

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 指代节点的下一连接。