92. Reverse Linked List II

Problem¶

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Solve¶

Linked-list only¶

O(n)

We do and done reverse the linked list, but only in one traversal. This accomplish by connecting the node to previous node on every step.

This is quite challenging when structuring:

• First, we get to left position of the linked list, while also save the begin node, which will connect to the last node being reversed.
  

      +---- left
      |
  [1, 2, 3, 4, 5]
   |
   +---- begin
  

  
  Code:
  

  i = 1;
  p = head;
  
  while (p != 0 && i < left) {
      i = i + 1;
      prev = p;
      p = p->next;
  }
  
  if (prev != 0)
      begin = prev;
  

• Next, we traversal till the right position, on every step, we link backward. Also, we saving the end node, which will be connect to the remain of the list.
  

      +---- end/left
      |
  [1, 2, 3, 4, 5]
   |
   +---- begin
  
   begin    end
   |        |
  [1, 4, 3, 2, 5]
      |        |
      right    remain
  

  
  This achieve by saving a lot temporary node.
  Code:
  

      while (p != 0 && i <= right) {
          // printf("%d, ", p->val);
          next = p->next;
          if (end == 0)
              end = p;
          else
              p->next = prev;
              i = i + 1;
              prev = p;
              p = next;
      }
      end->next = p;
      if (left == 1)
          return prev; // Special case, begin = NULL
      else
          begin->next = prev;
  

Final implementation:

/**

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    if (left == right) return head;

    struct ListNode *p = head;
    struct ListNode *prev = 0;
    struct ListNode *next = 0;
    struct ListNode *begin = 0;
    struct ListNode *end = 0;
    int i = 1;

    while (p != 0 && i < left) {
        i = i + 1;
        prev = p;
        p = p->next;
    }

    if (prev != 0)
        begin = prev;

    while (p != 0 && i <= right) {
        // printf("%d, ", p->val);
        next = p->next;
        if (end == 0)
            end = p;
        else
            p->next = prev;
        i = i + 1;
        prev = p;
        p = next;
    }

    end->next = p;
    if (left == 1)
        return prev;
    else
        begin->next = prev;
    return head;
}