Reverse Linked List II

Description

Reverse a linked list from position m to n.

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

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

Challenge:
Reverse it in-place and in one-pass We are here

Link

Lintcode_ladder

Method

1. find the pos of reversed region's begin, then perform reverse (n-m) times.
2. x

Example

1. 1

/**
 * 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) {
        // write your code here
        if (!head) {
            return nullptr;
        }
        // if (m = n) {
        //     return head;
        // }
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        // 0 1 2 3 4 5, m = 2
        // jump to 1
        // and get 1.next as start
        for (int i = 1; i < m; ++i) {
            prev = prev->next;
        } 
        ListNode* start = prev->next;
        for (int i = 0; i < n-m; ++i) {
            // 1 2 3 4 5, m=2 n=4
            // start = 2
            // tmp: 3
            // swap pos of 2,3
            ListNode* tmp = start->next;
            // start->next: 2.next -> 4
            start->next = tmp->next;
            // tmp->next: 3.next -> 2
            tmp->next = prev->next;
            // prev->next: 1.next -> 3
            prev->next = tmp;
        }
        return dummy.next;
    }
};

Similar problems

x

Tags

x