Leetcode日记：92&206.反转链表
92.反转链表其中一段
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
92-题目分析
也不知道Leetcode是怎么排布的题的顺序，但是唯一的可能是按题出现的频率，因为这个92题是II，206才是I。所以我们主要分析这道题。无非就是给你两个数，让你翻转第 M 个到底 N 个链表上的元素。
反转问题确实也是链表中常见的一种类型。而且这种题看似简单，但思考起来很容易搞乱。下面从代码的角度分析一下：
92-代码-1
代码一：节点插入
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
// create a dummy node to mark the head of this list
ListNode dummy = new ListNode(0);
dummy.next = head;
// make a pointer pre as a marker for the node before reversing
ListNode pre = dummy;
for(int i = 0; i<m-1; i++)
pre = pre.next;
// a pointer to the beginning of a sub-list that will be reversed
ListNode start = pre.next;
// a pointer to a node that will be reversed
ListNode then = start.next;
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i=0; i<n-m; i++){
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
return dummy.next;
}
92-代码分析
首先，我们利用给的 M ，找出第M个元素的位置，并将 M-1 位置标记为 pre ，M 标记为 start ，M+1 位置标记为 then ，然后执行第二个循环。
第二个循环的逻辑是交换节点，但是，我们并不是交换相邻的两个元素，而是将 then 换到 pre.next 的位置，这样才能达到翻转部分链表的目的：
-
循环找到第 M 个元素
第一次循环后 - 将
then换到pre.next
第二个循环执行一次 - 将
then后移一个
后移 -
继续循环
为了达到这个目的，我们要声明三个指针
- 第一个指向最后一个不需要反转的节点（第 M-1 个节点），相当于要反转链表部分的 dummy ，它负责找到头。
- 第二个指向第 M 个节点，它将是反转链表部分的最后一个节点，它负责找到尾。
- 以上这两个指针不应该移动，因为他们类似于 dummy 一头一尾，可以确定翻转边界。
- 第三个指针循环中移动，来使链表翻转。它负责元素移动。
92-代码-2
代码二：递归
class Solution {
// Object level variables since we need the changes
// to persist across recursive calls and Java is pass by value.
private boolean stop;
private ListNode left;
public void recurseAndReverse(ListNode right, int m, int n) {
// base case. Don't proceed any further
if (n == 1) {
return;
}
// Keep moving the right pointer one step forward until (n == 1)
right = right.next;
// Keep moving left pointer to the right until we reach the proper node
// from where the reversal is to start.
if (m > 1) {
this.left = this.left.next;
}
// Recurse with m and n reduced.
this.recurseAndReverse(right, m - 1, n - 1);
// In case both the pointers cross each other or become equal, we
// stop i.e. don't swap data any further. We are done reversing at this
// point.
if (this.left == right || right.next == this.left) {
this.stop = true;
}
// Until the boolean stop is false, swap data between the two pointers
if (!this.stop) {
int t = this.left.val;
this.left.val = right.val;
right.val = t;
// Move left one step to the right.
// The right pointer moves one step back via backtracking.
this.left = this.left.next;
}
}
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
this.recurseAndReverse(head, m, n);
return head;
}
}
92-代码-3
代码三：代码复用
这个方法是将部分链表翻转，转化为已知问题，也就是206转化一个完整链表问题。这样就可以将位置问题转化为已知问题，第二个循环完全是代码的复用。
public ListNode reverseBetween(ListNode head, int m, int n) {
// Empty list
if (head == null) {
return null;
}
// Move the two pointers until they reach the proper starting point
// in the list.
ListNode cur = head, prev = null;
while (m > 1) {
prev = cur;
cur = cur.next;
m--;
n--;
}
// The two pointers that will fix the final connections.
ListNode con = prev, tail = cur;
// Iteratively reverse the nodes until n becomes 0.
ListNode third = null;
while (n > 0) {
third = cur.next;
cur.next = prev;
prev = cur;
cur = third;
n--;
}
// Adjust the final connections as explained in the algorithm
if (con != null) {
con.next = prev;
} else {
head = prev;
}
tail.next = cur;
return head;
}
总结
这次的讲的是链表的翻转，可以用的思路有
- 递归、回溯
- 循环插入
链表问题在面试中被提问的可能性很大，而且题目变化种类不多，希望每讲一个问题，每个方法都记住。
更多关于链表的问题
更多关于链表的问题请转到链表标签
