[LeetCode] 92. Reverse Linked List II

轉自LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For 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.

<Solution>

Reverse Linked List 的衍生題，這次可以指定範圍來 reverse

解題想法如下(參考資料)

• 用個 dummy head，dummy->next 永遠指向最後答案的 head

• 找到要反轉起始位置的前一個 node，用指針 prv 記錄下來

• 要反轉起始位置，就是反轉後的最後一個 node，也用指針 reverseTail 記錄下來

• 把要反轉的 node 一個一個拿出去，並用 reverse order 的方式組合在一起，這之間都用指針 reverseHead 一直記錄 reverse linked list 的頭

• 將  reverseTail->next  指向 prv->next，然後再將 prv->next 指向 reverseHead

• 回傳 dummy->next

舉例

1  ->  2  ->  3  ->  4  ->  5  ->  6，m = 3, n = 5

則
initial:
                 prv
dummy  ->  1  ->  2  ->  3  ->  4  ->  5  ->  6

round 1:
                 prv
dummy  ->  1  ->  2   ->  4  ->  5  ->  6

           3
reverseHead，reverseTail

round 2:
                 prv
dummy  ->  1  ->  2  ->  5  ->  6

        4  ->  3
reverseHead  reverseTail

round 3:
                 prv
dummy  ->  1  ->  2  ->  6

        5  ->  4  ->  3
reverseHead       reverseTail

final:
                 prv
dummy  ->  1  ->  2  ->  5  ->  4  ->  3  ->  6
                    reverseHead    reverseTail

code 如下

	/**
	* 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) {
	if(!head || !head->next || m == n) {
	return head;
	}
	ListNode *dummy = new ListNode(-1);
	dummy->next = head;
	//> find previous node befor position m
	ListNode *prv = dummy, *curr = dummy;
	for(int i = 1; i <= m-1; i++) {
	curr = curr->next;
	}
	prv = curr;
	//> reverse nodes from position m to position n
	//> we extract nodes out and combine them in reverse order
	ListNode *reverseHead = NULL, *reverseTail = prv->next;
	for(int i = m; i <= n; i++) {
	curr = prv->next;
	prv->next = curr->next;
	curr->next = reverseHead;
	reverseHead = curr;
	}
	//> combine reverse linked list with remaining nodes
	reverseTail->next = prv->next;
	prv->next = reverseHead;
	return dummy->next;
	}
	};

view raw reverseSingleLinkedListII.cpp hosted with ❤ by GitHub