How to Reverse Linked List within Interval? (C/C++)

Reverse a linked list from position m to n. For example: Given 1-2-3-4-5-NULL, m = 2 and n = 4, return 1-4-3-2-5-NULL. 1 ≤ m ≤ n ≤ length of list.

In-place and One-pass

If we want to reverse a linked list, we can put the next node in the front one by one. For example,

A-B-C then B-A-C (put B in the front) then C-B-A (put C in the front).

So the implementation is straightforward, locate the m-th node from the start and put the nodes in the front n-m times.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto tail = head;
        ListNode* prev = NULL;
        for (int i = 0; i < m - 1; i ++) {
            prev = tail;
            tail = tail->next;
        }
        auto front = tail;
        for (int i = 0; i < n - m; i ++) {
            auto tmp = tail->next;
            tail->next = tail->next->next; 
            tmp->next = front;
            front = tmp;
            if (prev) {
                prev->next = front;
            }
        }
        return prev ? head : front;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —