【LeetCode练习题】Reverse Linked List II

雪柳花明 2016-09-28

展开全文

Reverse Linked List II
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.

题目意思：

翻转给定区间[m,n]的链表。

第一个节点m=1。

1<=m<=n<=length。

解题思路：

就我目前学习到的，有用指向指针的指针的，有插入，有逆转的。但是所有方法的核心，都其实是一个算法，就是利用3个指针修改区间内的节点的next值，且要保证已修改的链表是可以被找到的，即可以连入原链表中。

假设有一个链表有1,2,3,4,5,6，6个节点。m=2，n=5。

我们添加一个dummy节点，方便操作第一个节点。

首先让pre指向第m个节点前面那个，cur指向第m个节点，p1指向m的下一个节点，因为p1有可能是NULL，所以当p1不是NULL的时候，p2指向p1的下一个节点。

上图画出了这几个指针指向情况的开始状态和我们希望的终止状态。

在最终状态下，再通过其中方框中的两步就可以我们需要的链表了。

而cur，p1，p2三个指针在区间内向前移动并且将p1的next指向cur的过程则包含在一个for循环内部。如下：

代码如下：

 1 class Solution {
 2 public:
 3     ListNode *reverseBetween(ListNode *head, int m, int n) {
 4         ListNode *dummy = new ListNode(0);
 5         dummy->next = head;
 6 
 7         ListNode *pre = dummy, *cur = head;
 8         for(int i = 1; i < m; i++){
 9             pre = cur;
10             cur = cur->next;
11         }
12 
13         ListNode *p1,*p2;
14         if(cur)
15             p1 = cur->next;
16         if(p1)
17             p2 = p1->next;
18         for(int j = m; j < n; j++){
19             p1->next = cur;
20             cur = p1;
21             p1 = p2;
22             if(p2) p2 = p2->next;
23         }
24         pre->next->next = p1;
25         pre->next = cur;
26 
27         return dummy->next;
28     }
29 };