hot100之链表上

相交链表(160)

先看代码

1. public class Solution {
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         ListNode p = headA;
4.         ListNode q = headB;
6.         while (p != q){
7.             p = p != null ? p.next : headB;
8.             q = q != null ? q.next : headA;
9.         }
10.         return p;
11.     }
12. }

复制代码

• 分析
  

将A的尾节点与B相连, B的尾节点与A相连

据图可知当(p, q)→(A, B指针)步频一致时, 会共同到达共有链表的初节点
反转链表(206)

先看代码

1. class Solution {
2.     public ListNode reverseList(ListNode head) {
3.         ListNode prev = null;
4.         ListNode curr = head;
5.         while (curr != null){
6.             ListNode next = curr.next;
7.             curr.next = prev;
8.             prev = curr;
9.             curr = next;
10.         }
11.         return prev;
12.     }
13. }

复制代码

• 分析
  

通过先置哨兵节点, 避免节点数量过少导致null pointer exception
回文链表(234)

先看代码

1. class Solution {
2.     public boolean isPalindrome(ListNode head) {
3.         ListNode fast = head;
4.         ListNode slow = head;
6.         while (fast.next != null){
7.             fast = fast.next;
8.             slow = slow.next;
9.             if (fast.next != null){
10.                 fast = fast.next;
11.             }
12.         }
13.         ListNode rig = reverse(slow);
14.         ListNode lef = head;
15.         while (rig != null){
16.             if (rig.val != lef.val){
17.                 return false;
18.             }
19.             rig = rig.next;
20.             lef = lef.next;
21.         }
22.         return true;
24.     }
26.     private ListNode reverse(ListNode node){
27.         ListNode prev = null;
28.         while (node != null){
29.             ListNode next = node.next;
30.             node.next = prev;
31.             prev = node;
32.             node = next;
33.         }
34.         return prev;
35.     }
36. }

复制代码

• 分析
  

通过快慢指针找到中心节点,反转中心节点后链表,取(lef, rig)→(链表头尾节点) 进行回文分析
环形链表(141)

先看代码

1. public class Solution {
2.     public boolean hasCycle(ListNode head) {
3.         ListNode fast = head;
4.         ListNode slow = head;
6.         while (fast != null){
7.             fast = fast.next;
8.             slow = slow.next;
9.             
10.             if (fast != null){
11.                 fast = fast.next;
12.             }else return false;
14.             if (fast == slow) return true;
15.         }
16.         return false;
17.     }
18. }

复制代码

• 通过快慢指针, 快指针相对慢指针移动速度为1, 若有环, 必然追上慢指针
  

环形链表II(142)

先看代码

1. public class Solution {
2.     public ListNode detectCycle(ListNode head) {
4.         ListNode fast = head;
5.         ListNode slow = head;
7.         while (fast != null && fast.next != null){
8.             fast = fast.next.next;
9.             slow = slow.next;
10.             if (fast == slow) break;
11.         }
12.         if (fast == null || fast.next == null) {
13.             return null;
14.         }
15.         slow = head;
16.         while (slow != fast){
17.             fast = fast.next;
18.             slow = slow.next;
19.         }
20.         return slow;
21.     }
22. }

复制代码

• 分析
  

当快慢指针相遇时, 将慢指针置于head, 同步快慢指针步频, 再次相遇即为入口处

证明
f,  s 为快慢指针移动的步数
a, b分别为为环外长度, 环内长度
由 f = 2s, f = s + n∗b
有 f = 2n∗b, s = n∗b
因 f + a = 2n∗b + a 此时快指针指向环形链表入口
取p = head, 有 (p+a)%(n∗b) == (f+a)%(n∗b) == a
p 和 f在入口相遇

合并两个有序链表(021)

先看代码
[code]class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        ListNode p1 =list1;        ListNode p2 =list2;        ListNode dummy = new ListNode(-1) ;        ListNode res = dummy;        while(p1!= null && p2!=null){            if ( p1.val