[数据结构与算法]力扣算法学习day03-3

力扣算法学习day03-3

19-删除链表的倒数第N个结点

题目

代码实现

/**
 * 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 node = new ListNode(0,head);
        ListNode pre = node;
        ListNode cur = node;

        while(n-- >= 0){
            cur = cur.next;
        }

        while(cur != null){
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = pre.next.next;
        return node.next;
    }
}

面试题02.07.-链表相交

题目

代码实现

/**
 * 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) {
        int lengthA = 0;
        int lengthB = 0;
        ListNode nodeA = headA;
        ListNode nodeB = headB;

        // 首先计算两个链表的长度
        while(nodeA != null){
            nodeA = nodeA.next;
            lengthA++;
        }

        while(nodeB != null){
            nodeB = nodeB.next;
            lengthB++;
        }

        // 由于哪个长不确定，可以在思维上认为headA是更长的那个，并在判断后将headA指向长链表的头结点。
        // 顺带将长度之差求得。
        int length = 0;
        if(Math.max(lengthA,lengthB) == lengthA){
            nodeA = headA;
            nodeB = headB;
            length = lengthA - lengthB;
        } else {
            nodeA = headB;
            nodeB = headA;
            length = lengthB - lengthA;
        }

        // 然后将nodeA指针移动到尾部长度对齐位置。
        while(length > 0){
            nodeA = nodeA.next;
            length--;
        }

        // 对齐后，开始寻找交点
        while(nodeA != null){
            // 注意，这里判断的是结构，即指针，而不是值。
            if(nodeA == nodeB){
                return nodeA;
            }
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }

        return null;
    }

    // 力扣评论区大佬超简洁代码
    // 注：他这个方法的话，其实就是利用这个结构本身，两个指针一起走，短的链表先走完，然后把这个指针放在长的链表头上，
    // 然后继续两个指针一起走，当长的走到底后，同样的，放到短链表头上，这时，两个指针到结尾的长度就相等了，就可以开始
    // 寻找相交点了。
    // public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    //     ListNode h1 = headA, h2 = headB;

    //     while (h1 != h2) {

    //         h1 = h1 == null ? headB : h1.next;
    //         h2 = h2 == null ? headA : h2.next;
    //     }

    //     return h1;  
    // }
}

142-环形链表II

题目

代码实现

/**
 * 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) {
        /* 
         思路参考代码随想录，很棒。
         设入口距为x，相遇点退回入口的距离为y,相遇点经过环到入口距离为z
         慢指针到相遇点距离：x + y
         快指针到相遇点距离：x + y + n(y + z)
         慢指针速度为快指针的一半，故 2(x + y) = x + y + n(y + n)
         上式变形：x = (n - 1)(y + z) + z
         其中y + z为环形一圈，所以，去掉重复的圈数，则x = z
         故从距离上看，头结点到入口结点和相遇结点经环到入口结点的距离相同。
         */
        if(head == null){
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        // 找到相遇结点
        while(true){
            // 没有环，则返回null
            if(fast.next == null || fast.next.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                break;
            }
        }

        // 使slow重新指向头结点
        slow = head;
        // 找到入口结点
        while(true){
            if(fast == slow){
                return fast;
            }
            slow = slow.next;
            fast = fast.next;
        }
    }
}