Letcode-Top 100链表专题

《链表专题》

1.相交链表

• 方法一常规方法

根据链表A、B的差值，将较长的链表移动 差值的距离，然后两个链表同时向后移动，如果遇到相等的，则返回，否则返回空。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        Integer lengthA = 0;
        Integer lengthB = 0;
        Integer difference = 0;

        ListNode copyA = headA;
        ListNode copyB = headB;
        
        while(copyA.next!=null){
            copyA = copyA.next;
            lengthA++;
        }

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

        copyA = headA;
        copyB = headB;

        if(lengthA>=lengthB){
            difference = lengthA - lengthB;
            while(difference>0){
                copyA = copyA.next;
                difference--;
            }
        } else{
            difference = lengthB - lengthA;
             while(difference>0){
                copyB = copyB.next;
                difference--;
            }
        }

        while(copyA!=null && copyB!=null){
            if(copyA==copyB){
                return copyA;
            }

            copyA = copyA.next;
            copyB = copyB.next;
        }

        return null;
    }
}

• 方法二，哈希表

以空间换时间，将链表A的数据存储到哈希表中，循环链表B的数据判断两个链表的数据是否相等。

/**
 * 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) {

        HashSet<ListNode> set = new HashSet<>();
        ListNode copyA = headA;
        ListNode copyB = headB;
        while(copyA!=null){
            set.add(copyA);
            copyA = copyA.next;
        }

        while(copyB!=null){
            if(set.contains(copyB)){
                return copyB;
            }
            copyB = copyB.next;
        }

        return null;
        
    }
}

• 方法三：数学，逻辑，思维的方法

原理：若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。若不相交，a +b = b+a 。因此相遇处是NULL

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA;
        ListNode nodeB = headB;

        while(nodeA!=nodeB){
            nodeA = nodeA==null ? headB : nodeA.next;
            nodeB = nodeB==null ? headA : nodeB.next;
        }

        return nodeA;
    }
}

2.反转链表

• 常规方法

/**
 * 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 reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode newHead = new ListNode(0);
        ListNode curNode = head;

        while(curNode!=null){
            ListNode nextNode = curNode.next;
            curNode.next = newHead.next;
            newHead.next = curNode;
            curNode = nextNode;
        }


      return newHead.next;


    }
}

3.回文链表

• 方法一 反转后半部分链表

/**
 * 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 boolean isPalindrome(ListNode head) {

        if(head==null || head.next ==null){
            return true;
        }

        int k = 0;
        ListNode countNode = head;
        while(countNode!=null){
            k++;
            countNode = countNode.next;
        }

        ListNode middleHead = head;

        // 判断是奇数还是偶数,将链表一分为2
        int kk = 0;
        if(k%2==0){
            kk = k/2;
        }else{
            kk = k/2+1;
        }

        while(kk>0){
             middleHead = middleHead.next;
             kk--;
        }

        // 链表反转
        ListNode newHead = new ListNode(0);
        ListNode curNode = middleHead;
        while(curNode!=null){
            ListNode nextNode = curNode.next;
            curNode.next = newHead.next;
            newHead.next = curNode;
            curNode = nextNode;
        }

        middleHead = newHead.next;

        while(head!=null && middleHead!=null){
            if(head.val!=middleHead.val){
                return false;
            }
            head = head.next;
            middleHead = middleHead.next;
        }

        return true;
    }
}

• 方法二，以空间换时间

/**
 * 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 boolean isPalindrome(ListNode head) {
        int k = 0;
        ListNode curNode = head;
        List<ListNode> list = new ArrayList<>();
        while(curNode!=null){
            list.add(curNode);
            k++;
            curNode = curNode.next;
        }

        for(int i=0;i<k/2;i++){
            ListNode before = list.get(i);
            ListNode after  = list.get(k-i-1);
            if(before.val != after.val){
                return false;
            }
        }
        return true;

        

    }
}

4.环形链表

• 方法一：哈希表，ArrayList空间

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null){
            return false;
        }

        List<ListNode> list = new ArrayList();
        while(head!=null){
            if(list.contains(head)){
                return true;
            }
            list.add(head);
        
            head= head.next;
        }

        return false;
    }
}

• 方法二：快慢指针
  

在相同的时间内快指针走过的距离是慢指针的2倍，所以有
a+b+m*(b+c) = 2*(a+b+n*(b+c))

整理得到
a+b=(m-2n)(b+c)，

a+b=(m-2n)(b+c)这里没解释清楚感觉。a+b=(m-2n-1)(b+c)+b+c 两边同事去掉b得 a = (m-2n-1)(b+c) + c => a-c = (m-2n-1)(b+c) => a-c的长度差就是环长度的整数倍。第一种大环的情况下m=1 n=0 => a-c = 0 => a=c.如果一个从相交点开始跑，一个从头结点开始，速度一样，都是一个节点，那么假设相交则有从头开始的路程为a+x(b+c)+b,从相交点开始的路程为c+y(b+c)+b,由于速度一样，故路程一样得 a-c = (x-y)(b+c),也是整数倍，假设成立。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }

        // 环境
        ListNode slow = head;
        ListNode fast = head.next;

        while(slow!=fast){
            if(fast==null||fast.next==null){
                return false;
            }

            slow = slow.next;
            fast = fast.next.next;

        }

        return true;

        
    }
}

142. 环形链表 II

方法一：hashMap集合的方式

/**
 * 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) {

        HashSet<ListNode> set = new HashSet<>();
        ListNode node = head;
        while(node!=null){
            if(set.contains(node)){
                return node;
            }
            set.add(node);
            node = node.next;
        }
        return null;
        
    }
}

方法二：证明理解


上图黄色节点为快慢指针相遇的节点，此时

快指针走的距离：a+(b+c)n+b

很容易理解b+c为环的长度，a为直线距离，b为绕了n圈之后又走了一段距离才相遇，所以相遇时走的总路程为a+(b+c)n+b，合并同类项得a+(n+1)b+nc。

慢指针走的距离：a+(b+c)m+b,m代表圈数。

然后我们设快指针得速度是慢指针的2倍,含义为相同时间内，快指针走过的距离是慢指针的2倍。

**a+(n+1)b+nc=2[a+(m+1)b+mc]整理得a+b=(n-2m)(b+c)，**那么我们可以从这个等式上面发现什么呢？b+c

为一圈的长度。也就是说a+b等于n-2m个环的长度。为了便于理解我们看一种特殊情况，当n-2m等于1，那么a+b=b+c整理得，a=c此时我们只需重新释放两个指针，一个从head释放，一个从相遇点释放，速度相同，因为a=c所以他俩必会在环入口处相遇，则求得入口节点索引。

/**
 * 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) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (slow != null && fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                while (head != null && slow != null) {
                    if (head == slow) {
                        return head;
                    }
                    head = head.next;
                    slow = slow.next;
                }
            }

        }

        return null;

    }
}

21. 合并两个有序链表

• 常规方法

/**
 * 常规方法
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }

        if(list2==null){
            return list1;
        }

        // 比较大小
        ListNode newHead = new ListNode(0);
        ListNode curNode = newHead;

        ListNode nodeA = list1;
        ListNode nodeB = list2;
        while(nodeA!=null && nodeB!=null){
            if(nodeA.val<=nodeB.val){
                curNode.next = nodeA; 
                nodeA = nodeA.next;

            }else{
                curNode.next = nodeB;
                nodeB = nodeB.next;

            }
            curNode = curNode.next;
        }

        if(nodeA!=null){
            curNode.next = nodeA;
        }

            if(nodeB!=null){
            curNode.next = nodeB;
        }
        return newHead.next;
    }
}

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

1.先找到 链表的长度，然后根据链表长度获取数据

/**
 * 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) {

        int length = 0;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode curNode = newHead;

        ListNode headNode = head;
        while(head!=null){
            head = head.next;
            length++;

        }

        int size = length - n ;
        while(size>0){
            curNode = curNode.next;
            size--;
        }

        curNode.next = curNode.next.next;
        return newHead.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 newHead = new ListNode(0);
        newHead.next = head; 

        ListNode curNode = newHead;
        ListNode preNode = newHead;

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

        while(curNode.next!=null){
            curNode = curNode.next;
            preNode = preNode.next;
        }

        preNode.next = preNode.next.next;

        return newHead.next;
    }
}

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

方法一：常规方法 注意边界条件

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = new ListNode(0, head);
        ListNode curHead = newHead;

        while (curHead.next != null && curHead.next.next != null) {
            ListNode one = curHead.next;
            ListNode two = curHead.next.next;

            ListNode nextNode = two.next;
            two.next = one;
            one.next = nextNode;
            curHead.next = two;

            curHead = curHead.next.next;

        }

        return newHead.next;

    }
}

二、递归的方法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

25. K 个一组翻转链表

方法一：反转链表升级版

 class Solution {
        public static ListNode reverseKGroup(ListNode head, int k) {

            ListNode newHead = new ListNode(0,head);
            ListNode curNode = newHead;
            while(curNode!=null&& curNode.next!=null){
                // 首先判断是否有k个
                int temp = k;
                ListNode preNode = curNode;
                ListNode originalStartNode = curNode.next;
                ListNode endNode = originalStartNode;
                while(originalStartNode!=null && temp>0){
                    curNode = curNode.next;
                    originalStartNode = originalStartNode.next;
                    temp--;
                }

                if(temp>0){
                    break;
                }

                // 记录下Next节点
                ListNode nextNode = curNode.next;
                ListNode startNode =  convertNode(endNode,nextNode,k);
                preNode.next = startNode;
                endNode.next = nextNode;
                curNode = endNode;
            }

            return newHead.next;
        }

        // 反转链表
        public static ListNode  convertNode(ListNode startNode, ListNode nextNode, int k){

            ListNode head = new ListNode(0);
            
            ListNode curNode = startNode;
            while(curNode!=null &&  k>0){
                ListNode next = curNode.next;
                curNode.next = head.next;
                head.next = curNode;
                curNode = next;
                k--;
            }

            return head.next;

        }




    }

138. 随机链表的复制

方法一：迭代法

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }

        Node node = head;

        while (node != null) {
            Node tempNode = new Node(node.val);
            tempNode.next = node.next;
            node.next = tempNode;
            node = node.next.next;
        }

        node = head;
        // 循环拷贝
        while (node != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }

        node = head;

        Node result = head.next;

        // 循环链接

        Node preNode = head;
        Node curNode = head.next;
        while (curNode != null && curNode.next != null) {
            preNode.next = preNode.next.next;
            curNode.next = curNode.next.next;
            preNode = preNode.next;
            curNode = curNode.next;
        }
        preNode.next = null;
        return result;
    }
}

方法二：map

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {

        Map<Node,Node> map = new HashMap<Node,Node>();

        // 首先填充数据
        Node node = head;
        while(node!=null){
            Node tempNode = new Node(node.val);
            map.put(node,tempNode);
            node = node.next;
        }

        node = head;
        while(node!=null){
             map.get(node).next = map.get(node.next);
             map.get(node).random = map.get(node.random);
             node = node.next;
        }

        return map.get(head);


        
    }
}

148. 排序链表

方法一：以时间换空间

/**
 * 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 sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        int length = 0;
        ListNode node = head;
        while (node != null) {
            node = node.next;
            length++;
        }

        int[] array = new int[length];
        int i = 0;
        node = head;
        while (node != null) {
            array[i] = node.val;
            node = node.next;
            i++;
        }

        Arrays.sort(array);

        ListNode newHead = new ListNode(0);
        ListNode finalHead = newHead;
        for (int k : array) {
            ListNode listNode = new ListNode(k);
            newHead.next = listNode;
            newHead = newHead.next;
        }

        return finalHead.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 sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }

        if (head.next == tail) {
            head.next = null;
            return head;
        }

        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;

    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dumyHead = new ListNode(0);
        ListNode temp = dumyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }

        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }

        return dumyHead.next;

    }

}

方法三：归并排序，自下而上

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        ListNode dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummyHead, curr = dummyHead.next;
            while (curr != null) {
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                curr = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

23. 合并 K 个升序链表

方法一：常规方法

/**
 * 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 mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }

        if(lists.length==1){
            return lists[0];
        }

        // 循环合并两个有序链表
        ListNode ans = null;
        for(int i =0;i<lists.length;i++){
           ans =  mergeSort(ans,lists[i]);
        }

        return ans;

    }

    public ListNode mergeSort(ListNode one, ListNode two) {
        if (one == null) {
            return two;
        }

        if (two == null) {
            return one;
        }

        ListNode listOne = one;
        ListNode listTwo = two;
        ListNode node= new ListNode(0);
        ListNode newHead = node;
        while (listOne != null && listTwo != null) {
            if (listOne.val <= listTwo.val) {
                newHead.next = listOne;
                listOne = listOne.next;
            } else {
                newHead.next = listTwo;
                listTwo = listTwo.next;
            }
            newHead = newHead.next;
        }

        if (listOne != null) {
            newHead.next = listOne;
        }

        if (listTwo != null) {
            newHead.next = listTwo;
        }

        return node.next;

    }
}

方法二、常规方法升级版

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-k-sorted-lists/solutions/219756/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

146. LRU 缓存

方法一：参考宫水三叶 双链表 + map

class LRUCache {

    class Node {
        int k, v;
        Node l, r;

        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }

    int n;
    Node head, tail;
    Map<Integer, Node> map;

    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        // 首先判断数据是否存在
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            if (map.size() == n) {
                Node del = tail.l;
                map.remove(del.k);
                del(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }

        refresh(node);

    }

    public void refresh(Node node) {
        del(node);
        // 插入头部
        node.r = head.r;
        head.r = node;
        node.l = head;
        node.r.l = node;

    }

    public void del(Node node) {
        if (node.l == null) {
            return;
        }
        node.l.r = node.r;
        node.r.l = node.l;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */