代码随想录算法训练营第四天|24-19-160-142

LeetCode.24 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode sentinel = new ListNode (-1, head);
        if (sentinel.next != null) {
            swap(sentinel, sentinel.next, sentinel.next.next);
        }
        return sentinel.next;
    }

    private void swap (ListNode left, ListNode cur1, ListNode cur2) {
        // recursion exits when one of the pair is null
        if (cur1 == null || cur2 == null) {
            return;
        } else {
            // if both nodes are valid, record the next of cur2 and swap them 
            ListNode temp = cur2.next;
            left.next = cur2;
            cur2.next = cur1;
            cur1.next = temp;

            // cur1.next is the next first node to swap thus check whether it's valid
            // if so, recursivelly call this method, else exits
            if(cur1.next != null) {
                swap(cur1, cur1.next, cur1.next.next);
            }else{
                swap(cur1, null, null);
            }
        }
    }
}

LeetCode.19 删除链表的倒数第n个结点

class Solution {

    // public ListNode removeNthFromEnd(ListNode head, int n) {
    //     ListNode sentinel = new ListNode (-1, head);
    //     int cnt = 0;
    //     ListNode p = sentinel.next;
        
    //     // count how many nodes this list has
    //     while (p != null) {
    //         cnt++;
    //         p = p.next;
    //     }

    //     int index = cnt - n;
    //     p = sentinel;

    //     while (index > 0) {
    //         p = p.next;
    //         index--;
    //     }

    //     p.next = p.next.next;

    //     return sentinel.next;
    // }
    

    // space O(1) solution
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode (-1, head);
        ListNode slowIndex = sentinel, FastIndex = sentinel;

        // let fastIndex move n times first
        while (n > 0) {
            FastIndex = FastIndex.next;
            n--;
        }

        // then let both pointers move together
        // When fastIndex stops, slowIndex points to exactly the node that needs to be deleted.
        while (FastIndex.next != null) {
            FastIndex = FastIndex.next;
            slowIndex = slowIndex.next;
        }
        // now delete the node
        slowIndex.next = slowIndex.next.next;
        
        return sentinel.next;
    }
}

更新了一种双指针，空间复杂度O(1)的解决方法。

LeetCode.160 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        HashSet<ListNode> visited = new HashSet<>();

        while (pa != null) {
            visited.add(pa);
            pa = pa.next;
        }
        
        while (pb != null) {
            if (visited.contains (pb)) {
                return pb;
            }
            pb = pb.next;
        }

        return null;
    }
}

有空间复杂度O(1)的方法

public class Solution {
    // m = a + c, n = b + c, m + n = n + m, (a + c + b) + c = (b + c + a) + c
  	// thus if there is intersection, pointer A and B would meet at the node
  	// else they would meet at the end of each list
    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;
    }
}

LeetCode 142.环形链表

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slowIndex = head, fastIndex = head;
        
        while (fastIndex != null && fastIndex.next != null) {
            fastIndex = fastIndex.next.next;
            slowIndex = slowIndex.next;

            // there exists a circle
            if (fastIndex == slowIndex) {
                ListNode p = head;
                ListNode q = fastIndex;

                while (p != q) {
                    p = p.next;
                    q = q.next;
                }

                return p;
            }
        }

        return null;
    }

    /*
     * 假设链表的结构为X+X，分界点为环的相接点，则快指针刚好追上满指针，如果环的接入点不等分列表，用另外两个指针相遇
     * 进行相接点判断
     */
}