24.?兩兩交換鏈表中的節點

1. 迭代方法

public static ListNode swapPairs(ListNode head) {// 輸入：head = [1,2,3,4]// 輸出：[2,1,4,3]ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {ListNode tmp1 = cur.next;ListNode tmp2 = tmp1.next.next;// 交換邏輯cur.next = tmp1.next;tmp1.next.next = tmp1;tmp1.next = tmp2;// 更新指針cur = tmp1;}return dummy.next;
}

2. 遞歸方法

public static ListNode swapPairs(ListNode head) {// 遞歸寫法if (head == null || head.next == null) return head;ListNode rest = head.next.next;ListNode newHead = head.next;newHead.next = head;head.next = swapPairs(rest);return newHead;
}

19.?刪除鏈表的倒數第 N 個結點

• 快慢指針思想
• 先讓fast指針走n步，然后快慢指針同時移動，當快指針為null,則找到倒數第n個節點

public static ListNode removeNthFromEnd(ListNode head, int n) {// 讓快指針走n+1步，快慢指針同時移動，當快指針為null,則慢指針為要刪除節點的前一個節點(倒數第n+1個節點）ListNode dummy = new ListNode(-1);dummy.next = head;ListNode slow = dummy;ListNode fast = dummy;// 找倒數第n+1個節點for (int i = n+1; i > 0 && fast!=null; i--) {fast = fast.next;}while (fast != null) {slow = slow.next;fast = fast.next;}// 刪除倒數第n個節點slow.next = slow.next.next;// 返回頭節點return dummy.next;
}

面試題 鏈表相交

• 使用快慢指針方法

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {//給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。// 如果兩個鏈表沒有交點，返回 null// 設單鏈表A的長度為a，單鏈表B的長度為b，設他們公共的長度為c// a+b-c = b+a-c// 即兩個鏈表遍歷完自身后，再遍歷他們x單位便能找到公共節點ListNode pA = headA;ListNode pB = headB;if (pA == null || pB == null) return null;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;
}

142.?環形鏈表 II

• 當快慢節點相遇后，將快節點移動到鏈表頭部，快節點和慢節點相遇的地方就是入口

public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 找到環內某一點while (true) {if (fast == null || fast.next == null) return null;slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}// 找到入環點fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}