算法|两两交换链表中的节点、删除链表的倒数第 N 个结点、链表相

一、 24. 两两交换链表中的节点

题目连接：https://leetcode.cn/problems/swap-nodes-in-pairs/
思路一：使用迭代法

a318675992dc405e2e9c5a258afce2d.jpg

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur != null && cur.next != null){
           ListNode temp = cur.next.next;
           ListNode next = cur.next;
           next.next = cur;
           cur.next = temp;
           pre.next = next;
           pre = cur;
           cur = temp;
        }
        return dummy.next;
    }
}

思路二、使用递归方法

50c1d9c39f0162a73eb283489bb2d0a.jpg

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode temp = swapPairs(next.next);
        next.next = head;
        head.next = temp;
        return next;
    }
}

二、 19. 删除链表的倒数第 N 个结点

题目连接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路：fast从head先走n步，即fast = head, while (n-- > 0) fast = fast.next; slow从dummy开始走到fast==null时，此时slow是倒数n的前一个节点。在做删除slow.next = slow.next.next;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = head;
        ListNode slow = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

三、 02.07. 链表相交

题目连接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
思路：遍历统计两个链表的长度，让比较长的链表先走（lenA - lenB）步，然后两个指针一块走到最后，看指针是否有相同的，此题注意如果lenB > lenA 让两个数量交换，两个链表交互，总之lenA是比较长的那个

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if (lenB > lenA) {
            int temp = lenA;
            lenA = lenB;
            lenB = temp;
            ListNode tempListNode = curA;
            curA = curB;
            curB = tempListNode;
        }

        int gap = lenA - lenB;
        while (gap-- > 0) {
            curA = curA.next;
        }
        while (curA != null) {
            if (curA == curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

四、 142. 环形链表 II

题目连接：https://leetcode.cn/problems/linked-list-cycle-ii/
思路：使用快慢指针，fast 一次走两步，slow一次走一步，如果有环 fast会和slow相遇，相遇后，如图推论 x = z 即 temp 和 fast再次相遇即为入口

af1ae8de6999d5ccfd8a5246075ffdd.jpg

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode cur = head;
                while (cur != fast) {
                    fast = fast.next;
                    cur = cur.next;
                }
                return cur;
            }
        }
        return null;
    }
}