1、leetcode136.刪除鏈表的結點

給定單向鏈表的頭指針和一個要刪除的節點的值，定義一個函數刪除該節點。

返回刪除后的鏈表的頭節點。

示例 1:

輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為?5?的第二個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 1 -> 9.

示例 2:

輸入: head = [4,5,1,9], val = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為?1?的第三個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 5 -> 9.

① 雙指針求解

?

public ListNode deleteNode(ListNode head, int val) {//初始化一個虛擬節點ListNode dummy = new ListNode(0);//讓虛擬節點指向頭結點dummy.next = head;ListNode cur = head;ListNode pre = dummy;while (cur != null) {if (cur.val == val) {//如果找到要刪除的結點，直接把他刪除pre.next = cur.next;break;}//如果沒找到，pre指針和cur指針都同時往后移一步pre = cur;cur = cur.next;}//最后返回虛擬節點的下一個結點即可return dummy.next;
}

• 刪除一個結點，先獲取該結點的上一個結點?

?② 遞歸

public ListNode deleteNode(ListNode head,int val){if(head == null) return head;if(head.var == val) return head.next;head.next = deleteNode(head.next,val);return head;
}

?2、leetcode24.兩兩交換鏈表中的結點

給你一個鏈表，兩兩交換其中相鄰的節點，并返回交換后鏈表的頭節點。你必須在不修改節點內部的值的情況下完成本題（即，只能進行節點交換）。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

• 鏈表中節點的數目在范圍?[0, 100]?內
• 0 <= Node.val <= 100

?① 非遞歸

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0,head);ListNode temp = dummy;while(temp.next != null && temp.next.next != null){ListNode start = temp.next;ListNode end = temp.next.next;temp.next = end;start.next = end.next;end.next = start;temp = start;}return dummy.next;}
}

② 遞歸（沒看懂！）

class Solution {public ListNode swapPairs(ListNode head){  if(head == null ||  head.next == null){return head;}ListNode next = head.next;head.next =  swapPairs(next.next);next.next = head;return next;}
}

3、leetcode160.相交鏈表

給你兩個單鏈表的頭節點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回?null?。

圖示兩個鏈表在節點?c1?開始相交：

題目數據?保證?整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須?保持其原始結構?。

自定義評測：

評測系統?的輸入如下（你設計的程序?不適用?此輸入）：

• intersectVal?- 相交的起始節點的值。如果不存在相交節點，這一值為?0
• listA?- 第一個鏈表
• listB?- 第二個鏈表
• skipA?- 在?listA?中（從頭節點開始）跳到交叉節點的節點數
• skipB?- 在?listB?中（從頭節點開始）跳到交叉節點的節點數

評測系統將根據這些輸入創建鏈式數據結構，并將兩個頭節點?headA?和?headB?傳遞給你的程序。如果程序能夠正確返回相交節點，那么你的解決方案將被?視作正確答案?。

?

示例 ：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

?

提示：

• listA?中節點數目為?m
• listB?中節點數目為?n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果?listA?和?listB?沒有交點，intersectVal?為?0
• 如果?listA?和?listB?有交點，intersectVal == listA[skipA] == listB[skipB]

?

進階：你能否設計一個時間復雜度?O(m + n)?、僅用?O(1)?內存的解決方案？

① 雙指針

解題思路：設【第一個公共點】為 node，【鏈表 headA】的結點數量為 a，【鏈表? headB】的結點數量為 b，【兩鏈表的公共尾部】的節點數量為? c，則有：

• 頭節點 headA 到? node 前，共有? a - c 個節點；
• 頭節點 headB?到? node 前，共有? b?- c 個節點；

?考慮構建兩個節點指針 A , B 分別指向兩鏈表頭節點 headA，headB，做如下操作：

• 指針 A 先遍歷完鏈表 headA，再開始遍歷鏈表 headB，當走到 node 時，共走步數為：

a + (b - c)

• 指針 B 先遍歷完鏈表 headB，再開始遍歷鏈表 headA，當走到 node 時，共走步數為：

?b + (a - c）

• 如下式所示，此時指針 A ，B 重合，并有兩種情況：

a + (b - c) = b + (a - c)

1. 若兩鏈表有公共尾部（即 c > 0）：指針 A , B 同時指向【第一個公共節點】 node
2. 若兩鏈表無公共尾部（即 c = 0）：指針 A , B 同時指向 null

因此返回 A 即可。

public class Solution {public ListNode getIntersectionNode(ListNode headA,ListNode headB){if (headA == null || headB == null) {return null;}ListNode A = headA, B =  headB;while(A != B){A = A != null ? A.next : headB;;B = B != null ? B.next : headA;}return A;}
}

② 哈希集合

判斷兩個鏈表是否相交，可以使用哈希集合存儲鏈表節點。

首先遍歷鏈表 headA，并將鏈表 headA 中的每個節點加入哈希集合中。然后遍歷鏈表 headB，對于遍歷到的每個節點，判斷該節點是否在哈希集合中：

• 如果當前節點不在哈希集合中，則繼續遍歷下一個節點
• 如果當前節點在哈希集合中，則后面的節點都在哈希集合中，即從當前節點開始的所有結點都在兩個鏈表的相交部分，因此在鏈表 headB 中遍歷的第一個在哈希集合中的節點就是兩個量表相交的節點，返回該節點。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}