LeetCode 链表解题汇总 Java版

亦凉 2022-10-01 07:57 22阅读 0赞

# 19. Remove Nth Node From End of List (Medium) #

*  移除倒数第N个节点
 *  [19. Remove Nth Node From End of List][]
 *  代码：
    
     *  先判断经过n个节点后是否刚好到了末尾，是的话链表长度为n，第n个节点就是头结点，直接返回head.next的链表。
     *  经过n个节点后，还未到末尾，此时开启双指针，slow和fast同时往后走，fast和slow之间差距为n，fast到末尾，slow就是距离末尾n的节点，移除掉，返回head

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) {
            return head.next;
        }
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
    复制代码

# 21. Merge Two Sorted Lists (Easy) #

*  有序链表合并
 *  [21. Merge Two Sorted Lists][]
 *  代码：

class Solution {
    
        public  ListNode head;
        public  ListNode tail;
    
        public  ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            head = tail = null;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    add(l1);
                    l1 = l1.next;
                } else {
                    add(l2);
                    l2 =  l2.next;
                }
            }
            if (l1 != null) {
                add(l1);
            } else if (l2 != null) {
                add(l2);
            }
            return head;
        }
    
        public  void add(ListNode next) {
            if (head == null) {
                head = tail = next;
            } else {
                tail.next = next;
                tail = next;
            }
        }
    }
    复制代码

# 23. Merge k Sorted Lists (Hard) #

*  合并k个有序链表
 *  [23. Merge k Sorted Lists][]
 *  代码：分治算法将链表两两合并，最后合并成一个链表，平均一条链表n个节点，合并两条链表为O(n)，k条链表合并为O(logk)，合并为O(nlogk)

class Solution {
       public ListNode mergeKLists(ListNode[] lists) {
            if(lists == null || lists.length == 0) return null;
            return partion(lists, 0, lists.length - 1);
        }
    
        private ListNode partion(ListNode[] lists, int start, int end) {
            if(start == end) {
                return lists[start];
            }
            else if(start < end) {
                int mid = (start + end) / 2;
                ListNode l1 = partion(lists, start, mid);
                ListNode l2 = partion(lists, mid + 1, end);
                return merge(l1, l2);
            }
            else {
                //not gonna happen.
                return null;
            } 
        }
    
        private ListNode merge(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val < l2.val) {
                l1.next = merge(l1.next, l2);
                return l1;
            } else {
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }
    }
    复制代码

# 24. Swap Nodes in Pairs (Medium) #

*  交换链表相邻两个节点，只能修改引用，不允许修改节点的值
 *  [24. Swap Nodes in Pairs][]
 *  代码：

//新增一个哨兵头结点，通过哨兵节点简化代码
        public ListNode swapPairs(ListNode head) {
            ListNode result = new ListNode(0);
            result.next = head;
            ListNode last = result;
            ListNode temp;
            //当前节点后存在2个节点可以交换
            while (last.next != null && last.next.next != null) {
                temp = last.next.next;
                last.next.next = temp.next;
                temp.next = last.next;
                last.next = temp;
                last = last.next.next;
            }
            return result.next;
        }
    复制代码

# 61. Rotate List (Medium) #

*  给定一个链表，和一个非负数k，旋转链表k次，k是非负数

Example 1:
    Input: 1->2->3->4->5->NULL, k = 2
    Output: 4->5->1->2->3->NULL
    Explanation:
    rotate 1 steps to the right: 5->1->2->3->4->NULL
    rotate 2 steps to the right: 4->5->1->2->3->NULL
    
    Example 2:
    Input: 0->1->2->NULL, k = 4
    Output: 2->0->1->NULL
    Explanation:
    rotate 1 steps to the right: 2->0->1->NULL
    rotate 2 steps to the right: 1->2->0->NULL
    rotate 3 steps to the right: 0->1->2->NULL
    rotate 4 steps to the right: 2->0->1->NULL
    复制代码

*  [61. Rotate List][]
 *  代码：
    
     *  使用双指针法，fast循环向右移动k位，遇到结尾就从head重新开始，结束fast就是结果链表的头结点。此时slow指向head，fast和slow同时向右移动，直到fast.next为空，将fast.next指向head，slow.next置为空，即可得结果链表
     *  注意边界情况以及k对链表长度取余的优化

public ListNode rotateRight(ListNode head, int k) {
            if (head == null || k == 0 || head.next == null) {
                return head;
            }
            ListNode fast = head;
            for (int i = 0, count = 0; i < k; i++) {
                if (fast.next != null) {
                    fast = fast.next;
                    count++;
                } else {
                    k = k % (count+1);
                    i = -1;
                    fast = head;
                }
            }
            if (fast == head) {
                return head;
            }
            ListNode slow = head;
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            ListNode result = slow.next;
            fast.next = head;
            slow.next = null;
            return result;
        }
    复制代码

# 82. Remove Duplicates from Sorted List II (Medium) #

*  给定一个已排序的链表，删除所有重复的节=-。

Given a sorted linked list, delete all duplicates such that each element appear only once.
    
    Example 1:
    
    Input: 1->1->2
    Output: 1->2
    Example 2:
    
    Input: 1->1->2->3->3
    Output: 1->2->3
    复制代码

*  [82. Remove Duplicates from Sorted List II][]
 *  代码：

public static ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode sentinel = new ListNode(-1);
            sentinel.next = head;
            ListNode nodeA = sentinel;
            ListNode nodeB = nodeA.next.next;
            while (nodeB != null) {
                if (nodeA.next.val == nodeB.val) {
                    while (nodeB != null && nodeA.next.val == nodeB.val) {
                        nodeB = nodeB.next;
                    }
                    nodeA.next = nodeB;
                    if (nodeB != null) {
                        nodeB = nodeB.next;
                    }
                } else {
                    nodeA = nodeA.next;
                    nodeB = nodeB.next;
                }
            }
            return sentinel.next;
        }
    复制代码

# 83. Remove Duplicates from Sorted List (Easy) #

*  给定一个已排序的链表，删除多余的节点，使每个元素只出现一次

*  [83. Remove Duplicates from Sorted List][]
 *  代码：

public static ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode nodeA = head;
            ListNode nodeB = head.next;
            while (nodeB != null) {
                if (nodeA.val == nodeB.val) {
                    nodeB = nodeA.next = nodeB.next;
                } else {
                    nodeA = nodeB;
                    nodeB = nodeB.next;
                }
            }
            return head;
        }
    复制代码

# 160. Intersection of Two Linked Lists (Easy) #

*  找出两个单链表的交点
 *  [160. Intersection of Two Linked Lists][]
 *  要求:
    
    1.  没有交点时返回null；
    2.  不能改表链表结构；
    3.  可以假设链表不成环；
    4.  时间复杂度O(n)，空间复杂度O(1)。

A:          a1 → a2
                        ↘
                          c1 → c2 → c3
                        ↗
    B:    b1 → b2 → b3
    复制代码

*  思路：
    
     *  链表A的长度为a+c，链表B的长度为b+c，c为公共部分长度，所以有a+c+b=b+c+a，即指针先走完A链表然后继续从B链表头开始走，B指针走完B链表然后从A链表头开始走，如果两个链表相交，那么A、B两个指针就会在共同链表相遇
 *  代码：

public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //任何一个链表为空都可以返回null
        if (headA == null || headB == null) {
            return null;
        }
        //记住A指针到达链表尾部的次数
        //当次数为2时，表示已到了链表B的尾部，此时还未相交就可以返回null
        int count = 0;
        ListNode l1 = headA, l2 = headB;
        while (l1 != l2) {
            if (l1 == null) {
                count++; //到达链表末尾则计数器加1
                if (count == 2) { //两次到达链表末尾都没相交，返回null
                    return null;
                }
                l1 = headB;
            } else {
                l1 = l1.next;
            }
            l2 = l2 == null ? headA : l2.next;
        }
        return l1;
    }
    复制代码

# 206. Reverse Linked List (Easy) #

*  链表翻转
 *  [206. Reverse Linked List][19. Remove Nth Node From End of List]
 *  分别使用循环和递归实现
 *  代码：

//普通循环
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp;
        ListNode newHead = null;
        while (head.next != null) {
            temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        head.next = newHead;
        return head;
    }
    
    //普通循环-使用哨兵简化代码
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp;
        ListNode newHead = new ListNode(0);
        while (head != null) {
            temp = head.next;
            head.next = newHead.next;
            newHead.next = head;
            head = temp;
        }
        return newHead.next;
    }
    
    //递归
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode newHead = reverseList(next);
        head.next = null;
        next.next = head;
        return newHead;
    }
    复制代码

# 24. Remove Nth Node From End of List (Medium) #

*  移除倒数第N个节点
 *  代码：
    
     *  先判断经过n个节点后是否刚好到了末尾，是的话链表长度为n，第n个节点就是头结点，直接返回head.next的链表。
     *  经过n个节点后，还未到末尾，此时开启双指针，slow和fast同时往后走，fast和slow之间差距为n，fast到末尾，slow就是距离末尾n的节点，移除掉，返回head

转载于:https://juejin.im/post/5cbc8481e51d456e6e389243

[19. Remove Nth Node From End of List]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Freverse-linked-list
[21. Merge Two Sorted Lists]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fmerge-two-sorted-lists%2Fdescription%2F
[23. Merge k Sorted Lists]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fmerge-k-sorted-lists%2F
[24. Swap Nodes in Pairs]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fswap-nodes-in-pairs%2F
[61. Rotate List]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Frotate-list%2F
[82. Remove Duplicates from Sorted List II]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fremove-duplicates-from-sorted-list-ii%2F
[83. Remove Duplicates from Sorted List]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fremove-duplicates-from-sorted-list%2F
[160. Intersection of Two Linked Lists]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fintersection-of-two-linked-lists%2F