92. Reverse Linked List II [LeetCode]

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

反转m到n之间的链表,下标从1开始,下标最大是链表的大小。


/*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) {
		//要求1<=m<=n
		//在head头部添加一个dummy节点,把dummy挂到head头部
		ListNode dummy(-1);
		dummy.next = head;

		ListNode *prev = &dummy;
		for (int i = 1; i < m ; ++i)
			prev = prev->next;
		ListNode* const head2 = prev;


		prev = head2->next;
		ListNode *cur = prev->next;

		for (int i = m; i < n; ++i) {
			prev->next = cur->next;
			cur->next = head2->next;
			head2->next = cur; 
			cur = prev->next;
		}
		return dummy.next;
	}
};

为了处理边界m=1的情况,在链表前面挂载一个dummy节点。

代码的核心:

			prev->next = cur->next;
			cur->next = head2->next;
			head2->next = cur; 
			cur = prev->next;

head2指针:反转序列的前一个节点(下标为 的前一个节点)

prev指针:开始反转的节点(指向下标为 的元素并在遍历中保持不变).

每次循环:head2的next指向当前cur,prev的next指向更新之后要处理的cur


画个图理解了一下,表示更加深刻了,请看我画的图:

根据题目给的Example画的

一句代码对应一张图,清晰明了程序的运行原理






版权声明:本文为MC_007原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/MC_007/article/details/80381774