【leetcode】链表part2

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;}