Reverse Linked List解题报告

Reverse Linked List

题目大意：把当前的linked list顺序颠倒

思路： 1. a，b交换值 a＝temp

　　　　　　　　　　temp ＝ b

　　　　　　　　　　b ＝ a

　　　2.用一个while循环，不断把当前拿到的值放在新的linked list的头上

　　　3.注意循环结束条件和指针的变化

代码：

 1 public ListNode reverse(ListNode head) {
 2         if (head == null) {
 3             return head;
 4         }
 5         ListNode current = new ListNode(0);
 6         ListNode temp = new ListNode(0);
 7         ListNode pre = new ListNode(0);
 8 
 9         pre = null;
10         current = head;
11         while (current != null) {
12             temp = current.next;
13             current.next = pre;
14             pre = current;
15             current = temp;
16         }
17         return pre;
18     }
19 }

注意点： 1. 原有的linked list最前面加一个null节点

　　　　2. 循环条件为current ！＝ null

　　　　3.返回值为pre pointer 而不是current pointer

Reverse Linked List ii

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return1->4->3->2->5->NULL.

题目大意：反转linked list 第m个点到第n个点的部分

思路：1. 分成前半部分，后半部和中间反转的部分。

　　　2.处理完中间反转部分后，把头，尾分别的反转部分的头尾相连。

　　　3.千万注意，m可能为1，即最后return的head不一定是最初的head。

　　　对于利用dummy node 一定有以下三句话：

　　　ListNode dummy = new ListNode(0);

　　　dummy.next = head;

　　　.....

　　　return dummy.next;

我的代码：

 1 public class Solution {
 2     public ListNode reverseBetween(ListNode head, int m , int n) {
 3         
 4         //locate the mth node
 5         ListNode dummy = new ListNode(0);
 6         dummy.next = head;
 7         ListNode preNode = dummy;
 8         ListNode current = head;
 9         int count;
10         for (count = 1; count < m; count++){
11             preNode = current;
12             if (current.next == null) {
13                 return null;
14             }
15             current = current.next;
16         }
17         
18         //reverse m to n
19         ListNode mNode = current;
20         ListNode pre = current;
21         current = current.next;
22         ListNode nNode;
23         for (count = m + 1 ;count <= n; count++) {
24             if (current == null) { 
25                 return null;
26             }
27             ListNode temp = current.next;
28             current.next = pre;
29             pre = current;
30             current = temp;
31         }
32         nNode = pre;
33         ListNode postNode = current;
34         
35         //link head and trail with reserved list
36         current = dummy;
37         for(int i = 1; i < m; i++) {
38             current = current.next;
39         }
40         current.next = nNode;
41         mNode.next = postNode;
42         return dummy.next;
43     }
44 }

九章代码：

 1 public class Solution {
 2     public ListNode reverseBetween(ListNode head, int m, int n) {
 3         if (m >= n || head == null) {
 4             return head;
 5         }
 6         
 7         ListNode dummy = new ListNode(0);
 8         dummy.next = head;
 9         head = dummy;
10         
11         for (int i = 1; i < m; i++) {
12             if (head == null) {
13                 return null;
14             }
15             head = head.next;
16         }
17         
18         ListNode premNode = head;
19         ListNode mNode = head.next;
20         ListNode nNode = mNode, postnNode = mNode.next;
21         for (int i = m; i < n; i++) {
22             if (postnNode == null) {
23                 return null;
24             }
25             ListNode temp = postnNode.next;
26             postnNode.next = nNode;
27             nNode = postnNode;
28             postnNode = temp;
29         }
30         mNode.next = postnNode;
31         premNode.next = nNode;
32         
33         return dummy.next;
34     }
35 }

反思：1.九章的代码，用了postnNode作为游走的current node，减少的变量的数目。

　　　2.用mNode和premnode nNode和postnNode 这样更加清晰　

dummy node总结：

当不确定头是什么东西的时候，用dummy node

用于－删除

　　－reverse

　　－merge

　　－partition