1.找出兩個鏈表的交點

160. Intersection of Two Linked Lists (Easy)

Leetcode?/?力扣

例如以下示例中 A 和 B 兩個鏈表相交于 c1：

A:          a1 → a2↘c1 → c2 → c3↗
B:    b1 → b2 → b3

但是不會出現(xiàn)以下相交的情況，因為每個節(jié)點只有一個 next 指針，也就只能有一個后繼節(jié)點，而以下示例中節(jié)點 c 有兩個后繼節(jié)點。

A:          a1 → a2       d1 → d2↘  ↗c↗  ↘
B:    b1 → b2 → b3        e1 → e2

要求時間復(fù)雜度為 O(N)，空間復(fù)雜度為 O(1)。如果不存在交點則返回 null。

設(shè) A 的長度為 a + c，B 的長度為 b + c，其中 c 為尾部公共部分長度，可知 a + c + b = b + c + a。

當訪問 A 鏈表的指針訪問到鏈表尾部時，令它從鏈表 B 的頭部開始訪問鏈表 B；同樣地，當訪問 B 鏈表的指針訪問到鏈表尾部時，令它從鏈表 A 的頭部開始訪問鏈表 A。這樣就能控制訪問 A 和 B 兩個鏈表的指針能同時訪問到交點。

如果不存在交點，那么 a + b = b + a，以下實現(xiàn)代碼中pa和pb會同時為 null，從而退出循環(huán)。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa = headA, pb = headB;while(pa != pb){pa = (pa == null ? headB : pa.next);pb = (pb == null ? headA : pb.next);}return pa;}
}

2.翻轉(zhuǎn)鏈表

206. Reverse Linked List (Easy)

Leetcode?/?力扣

雙指針迭代
我們可以申請兩個指針，第一個指針叫 pre，最初是指向 null 的。
第二個指針 cur 指向 head，然后不斷遍歷 cur。
每次迭代到 cur，都將 cur 的 next 指向 pre，然后 pre 和 cur 前進一位。
都迭代完了(cur 變成 null 了)，pre 就是最后一個節(jié)點了。

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while(cur != null){ListNode tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}
}

3.歸并兩個有序的鏈表

21. Merge Two Sorted Lists (Easy)

Leetcode?/?力扣

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 = list1, p2 = list2;ListNode list3 = new ListNode(-1), p3 = list3;while(p1 != null && p2 != null){if(p1.val <= p2.val){p3.next = p1;p3 = p3.next;p1 = p1.next;}else{p3.next = p2;p3 = p3.next;p2 = p2.next;}}if(p1 != null){p3.next = p1;}else{p3.next = p2;}return list3.next;}
}

4. 從有序鏈表中刪除重復(fù)節(jié)點

83. Remove Duplicates from Sorted List (Easy)

Leetcode?/?力扣

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode p = head;while(p.next != null){if(p.val == (p.next).val){p.next = p.next.next;}else{p = p.next;}}return head;}
}