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:

1
2
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

代码一:节点插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 的位置,这样才能达到翻转部分链表的目的:

  1. 循环找到第 M 个元素
    第一次循环后
    第一次循环后
  2. then 换到 pre.next
    第二个循环执行一次
    第二个循环执行一次
  3. then后移一个
    后移
    后移
  4. 继续循环
    第二个循环执行两次
    第二个循环执行两次

为了达到这个目的,我们要声明三个指针

  • 第一个指向最后一个不需要反转的节点(第 M-1 个节点),相当于要反转链表部分的 dummy ,它负责找到头
  • 第二个指向第 M 个节点,它将是反转链表部分的最后一个节点,它负责找到尾
  • 以上这两个指针不应该移动,因为他们类似于 dummy 一头一尾,可以确定翻转边界。
  • 第三个指针循环中移动,来使链表翻转。它负责元素移动

92-代码-2

代码二:递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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转化一个完整链表问题。这样就可以将位置问题转化为已知问题,第二个循环完全是代码的复用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
}

总结

这次的讲的是链表的翻转,可以用的思路有

  • 递归、回溯
  • 循环插入

链表问题在面试中被提问的可能性很大,而且题目变化种类不多,希望每讲一个问题,每个方法都记住。

更多关于链表的问题

更多关于链表的问题请转到链表标签