LeetCode入门指南之链表

83. 删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if (head == null) {

            return head;

        }

        //删除重复元素但保留一个的情况下头结点不可能被删除，故不需要哑结点

        ListNode cur = head;

        /**

         *      拿当前结点和当前结点后继结点比较,

         *      若后继结点与当前结点值相同则删除后继结点,

         *      否则cur后移，直到 cur.next 为 null

         */

        while (cur.next != null) {

            if (cur.next.val == cur.val) {

                //删除后继结点后无需后移，否则会漏过连续重复结点（3个及以上重复结点的情况）

                cur.next = cur.next.next;

            } else {

                cur = cur.next;

        }

        return head;

    }

}

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if (head == null) {

            return head;

        }

        //删除所有重复元素，当头结点为重复元素时要删除头结点，所以需要哑结点

        ListNode dummy = new ListNode(-1);

        //哑结点指向头结点

        dummy.next = head;

        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {

            //发现重复元素

            if (cur.next.val == cur.next.next.val) {

                //重复值

                int tempVal = cur.next.val;

                ListNode temp = cur.next.next;

                //找到最后一个重复元素

                while(temp.next != null && temp.next.val == tempVal) {

                    temp = temp.next;

                }

                //删除所有重复元素

                cur.next = temp.next;

            } else {

                cur = cur.next;

            }

        }

        return dummy.next;

    }

}

206. 反转链表

反转一个单链表。

思路一：迭代法：

/**

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

        //始终指向当前结点的前一个结点

        ListNode pre = null;

        //当前结点

        ListNode cur = head;

        while (cur != null) {

            //用来保存当前结点的下一个结点

            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

思路二：递归（锻炼递归思维）：

首先给出函数定义，如此题：ListNode reverseList(ListNode head)
1. 反转以head为头结点的链表
2. 返回反转后链表的头结点
不要用脑袋去模拟递归栈，根据函数的定义去处理递归的子问题，要具体到一个结点要做的事情
确定base case

class Solution {

    public ListNode reverseList(ListNode head) {

        if (head == null) {

            return head;

        }

        //base case, 当链表只有一个结点时退出递归

        if (head.next == null) {

            return head;

        }

        /**

         * 具体到头结点来说，反转当前链表只需要两步：

         *  1.反转以head.next为头的链表

         *  2.将head插入head.next为头的链表反转之后的链表末尾

         */

        ListNode vhead = reverseList(head.next); //根据递归函数定义，返回反转之后的链表头

        //反转之后head.next位于链表尾部，将head插入head.next之后

        head.next.next = head;

        head.next = null;

        return vhead;

    }

}

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (head == null) {

            return head;

        }

        //可能从第一个结点开始反转，故需要哑结点

        ListNode dummyNode = new ListNode(-1);

        dummyNode.next = head;

        //找到left之前和right之后的结点以便反转后拼接

        ListNode l = dummyNode, r = dummyNode;

        for (int i = 0; i < left - 1; i++) {        //l为left的前一个结点

            l = l.next;

        }

        for (int i = 0; i < right + 1; i++) {       //r为right后一个结点

            r = r.next;

        }

        ListNode last = reverse(l.next, r);

        l.next.next = r;

        l.next = last;

        return dummyNode.next;

    }

    //反转以left开头，right结尾的链表(左闭右开)，返回反转后的链表头结点

    private ListNode reverse(ListNode left, ListNode right) {

        ListNode pre = null, cur = left, next = left;

        while (cur != right) {

            next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

当头节点不确定是否会被操作的时候，使用哑巴节点

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

递归解法（锻炼递归思维）：

class Solution {

    /** 明确递归函数的定义：

     *      k个一组反转以head为头结点的链表，并返回反转后的头结点

     */

    public ListNode reverseKGroup(ListNode head, int k) {

        if (head == null) {

            return head;

        }

        /**

         *  按照递归函数定义，对第一组结点来说，k个一组反转整个链表分为两步：

         *      1.反转第一组结点

         *      2.将反转后的第一组结点与反转后的其他组结点拼接

         */

        //找到一组共k个结点，l为第1个结点，r为第k个结点的后一个结点,因为reverse的参数为左闭右开

        ListNode l = head, r = head;

        //移动k次后，r指向第k+1个点

        for (int i = 0; i < k; i++) {

            //base case, 当结点结点不足k个时，无需反转直接返回

            if (r == null) return l;

            r = r.next;

        }

        ListNode newHead = reverse(l, r);

        //反转后第一组的头结点变为尾结点

        l.next = reverseKGroup(r, k);

        return newHead;

    }

    //翻转left和right之间的结点，左闭右开

    private ListNode reverse(ListNode left, ListNode right) {

        ListNode pre = null, cur = left;

        while (cur != right) {

            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

递归解法（锻炼递归思维）：

class Solution {

    /**

     *  定义：

     *      合并链表l1， l2，返回合并后的链表

     */

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        //base case

        //若l1或l2为空，说明l1或l2为空链表，直接返回另外一个链表即为合并后的链表

        if (l1 == null) return l2;

        if (l2 == null) return l1;

        /**

         * 按照递归函数定义，对当前结点l1， l2来说，合并链表分为两部：

         *      1.若l1.val 小于 l2.val，只需将l1.next 和 l2合并之后的链表拼接在l1之后

         *      2.反之将l2.next 和 l1 合并之后的链表拼接在l2之后

         */

        if (l1.val < l2.val) {

            l1.next = mergeTwoLists(l1.next, l2);

            return l1;

        } else {

            l2.next = mergeTwoLists(l1, l2.next);

            return l2;

        }

    }

}

迭代解法：

提示：迭代法根据代码在本子上画一下很容易理解

class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode dummyNode = new ListNode(-1);

        ListNode pre = dummyNode;

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {

                pre.next = l1;

                l1 = l1.next;

            } else {

                pre.next = l2;

                l2 = l2.next;

            }

            pre = pre.next;

        }

        //l1还有剩余

        if (l1 != null) {

            pre.next = l1;

        } else {

            pre.next = l2;

        }

        return dummyNode.next;

    }

}

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

class Solution {

    /**

     *  审题：将链表中小于目标值的结点全部放置在大于等于目标值的结点之前。

     *      显然，可以遍历原来的链表时将链表分为两个链表，一个链表存储所有小于目标值的结点（相对顺序不变），

     *      另一个链表存储所有大于等于目标值的结点（相对顺序不变）;

     *      最后将大的链表拼接在小的链表之后。

     */

    public ListNode partition(ListNode head, int x) {

        if (head == null) {

            return head;

        }

        //创建两个哑结点，使用尾插法建立新链表 (头插法会改变相对顺序)

        ListNode smallDummy = new ListNode(-1);

        ListNode bigDummy = new ListNode(-1);

        ListNode smallPre = smallDummy;

        ListNode bigPre = bigDummy;

        //遍历链表

        ListNode cur = head;

        while (cur != null) {

            if (cur.val < x) {

                smallPre.next = cur;

                smallPre = smallPre.next;

            } else {

                bigPre.next = cur;

                bigPre = bigPre.next;

            }

            cur = cur.next;

        }

        //bigPre.next可能不为null

        bigPre.next = null;

        //拼接

        smallPre.next = bigDummy.next;

        return smallDummy.next;

    }

}

147. 对链表进行插入排序

对链表进行插入排序。

class Solution {

    /**

     *      插入排序思路：

     *              用last指针标识已经有序部分的最后一个结点；

     *              遍历剩余无序结点，依次插入有序部分；

     *              初始第一个结点为有序结点。

     *

     */

    public ListNode insertionSortList(ListNode head) {

        //没有结点或只有一个结点

        if (head == null || head.next == null) {

            return head;

        }

        //方便在头结点之前插入

        ListNode dummy = new ListNode(-1);

        dummy.next = head;

        ListNode last = head;

        ListNode cur = head.next;

        while (cur != null) {

            //若当前结点大于等于有序部分的最后一个结点则说明本身有序，直接将last后移

            if (cur.val >= last.val) {

                last = cur;

                cur = cur.next;

            } else {

                //在有序部分中找到插入的位置

                ListNode pre = dummy;

                while(pre.next.val < cur.val) {

                    pre = pre.next;

                }

                //cur插入时会修改next

                ListNode next = cur.next;

                //插入

                cur.next = pre.next;

                pre.next = cur;

                last.next = next;

                cur = next;

            }

        }

        return dummy.next;

    }

}

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

归并排序(空间复杂度为O(nlogn))：

class Solution {

    public ListNode sortList(ListNode head) {

        //base case 没有或者只有一个结点，退出递归

        if (head == null || head.next == null) {

            return head;

        }

        ListNode mid = getMidNode(head);

        ListNode rightHead = mid.next;

        //切断

        mid.next = null;

        //分别对左右两个链表进行归并排序

        ListNode left = sortList(head);

        ListNode right = sortList(rightHead);

        //合并后返回

        return mergeList(left, right);

    }

    //使用快慢指针寻找链表中点

    private ListNode getMidNode(ListNode head) {

        //该初始化方式得到的结果中：

        //当结点有偶数个时，slow指向两个中间结点的前一个结点;

        //当结点有奇数个时，slow指向中间结点。

        ListNode slow = head;

        ListNode fast = head.next;

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    //合并两个有序链表

    private ListNode mergeList(ListNode l1, ListNode l2) {

        if (l1 == null) return l2;

        if (l2 == null) return l1;

    	if (l1.val < l2.val) {

            l1.next = mergeList(l1.next, l2);

            return l1;

        } else {

            l2.next = mergeList(l1, l2.next);

            return l2;

        }

    }

}

快速排序：

class Solution {

    public ListNode sortList(ListNode head) {

        if (head == null) {

            return head;

        }

        return quickSort(head, null);

    }

    //对head开头，end结尾的链表进行快排(左闭右开)，返回排序后的结点

    private ListNode quickSort(ListNode head, ListNode end) {

        //base case, 没有结点或只有一个结点默认有序，退出递归

        if (head == end || head.next == end) {

            return head;

        }

        ListNode left = head, right = head;     //pivot为head

        ListNode cur = head.next;               //用来遍历剩余结点

        while (cur != end) {

            if (cur.val <= head.val) {          //头插法将小于等于pivot的结点放置在pivot之前

                //cur.next 被改变，先保存下来

                ListNode next = cur.next;

                cur.next = left;

                left = cur;

                cur = next;

            } else {                            //尾插法将大于pivot的结点放置在pivot之后

                right.next = cur;

                right = cur;

                cur = cur.next;

            }

        }

        right.next = end; //此步很重要

        ListNode vhead = quickSort(left, head);

        head.next = quickSort(head.next, end);

        return vhead;

    }

}

143. 重排链表

给定一个单链表 L：L₀ →L₁ →…→L_n-1 →L_n ，

将其重新排列后变为： L₀ →L_n →L₁ →L_n-1 →L₂ →L_n-2 →…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {

    /**

     *  思路：

     *      找到中点，反转后半部分，然后交叉合并为一个链表

     */

    public void reorderList(ListNode head) {

        //没有或只有1、2个结点无需操作

        if (head == null || head.next == null || head.next.next == null) {

            return;

        }

        ListNode midNode = getMidNode(head);

        ListNode nextHalf = midNode.next;

        midNode.next = null;    //切断前后两部分连接

        //反转后半部分链表

        ListNode nHead = reverse(nextHalf);

        //合并链表

        boolean flag = true;

        ListNode l1 = head, l2 = nHead;

        while (l2 != null) {

            if (flag) {

                ListNode next = l1.next;

                l1.next = l2;

                l1 = next;

            } else {

                ListNode next = l2.next;

                l2.next = l1;

                l2 = next;

            }

            flag = !flag;

        }

    }

    private ListNode getMidNode(ListNode head) {

        ListNode slow = head;

        ListNode fast = head.next;

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    private ListNode reverse(ListNode head) {

        ListNode pre = null;

        ListNode cur = head;

        while (cur != null) {

            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

如果链表中存在环，则返回 true 。否则，返回 false 。

public class Solution {

    /**

     *  思路：

     *      快慢指针，若慢指针最终追上快指针说明有环

     */

    public boolean hasCycle(ListNode head) {

        //没有或只有一个结点说明没有环

        if (head == null || head.next == null) {

            return false;

        }

        ListNode slow = head;

        ListNode fast = head.next;

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

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast) {

                return true;

            }

        }

        return false;

    }

}

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

思路：快慢指针，快慢指针相遇后，慢指针回到头，快慢指针步伐一致一起移动，相遇点即为入环点。有兴趣的可以自己看下官方题解中的推导。

/**

 * 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.next;

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

            fast = fast.next.next;

            slow = slow.next;

            if (slow == fast) {

                //快指针从第一次相交点下一个节点开始移动, 慢指针重新从头开始移动

                fast = fast.next;  //注意

                slow = head;

                while (fast != slow) {

                    fast = fast.next;

                    slow = slow.next;

                }

                // 相遇点即为入环点

                return fast;

            }

        }

        return null;

    }

}

234. 回文链表

请判断一个链表是否为回文链表。

思路：快慢指针找到中点，反转后半部分，然后依次比较，最后要记得还原链表

/**

 * 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;

        }

        ListNode mid = getMidNode(head);

        ListNode rHead = reverse(mid.next);

        //切断

        mid.next = null;

        ListNode lTemp = head;

        ListNode rTemp = rHead;

        //右半部分链表长度小于等于左半部分链表长度

        while (rTemp != null) {

            if (lTemp.val != rTemp.val) {

                return false;

            }

            lTemp = lTemp.next;

            rTemp = rTemp.next;

        }

        //还原

        mid.next = reverse(rHead);

        return true;

    }

    //对于偶数个结点和奇数个结点，slow都位于右部分的前一个结点

    private ListNode getMidNode(ListNode head) {

        ListNode slow = head;

        ListNode fast = head.next;

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    //反转链表

    private ListNode reverse(ListNode head) {

        ListNode pre = null, cur = head, next = head;

        while (cur != null) {

            next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

}

推荐使用slow = head;fast = head.next;的方式使用快慢指针
该方式下，结点个数为奇数，slow指向中点；结点个数为偶数，slow指向左边中点

138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

class Solution {

    public Node copyRandomList(Node head) {

        if (head == null) {

            return head;

        }

        //第一次遍历：先复制所有结点，占时不管指针域,并将新旧结点通过HashMap关联起来

        Node cur = head;

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

        while (cur != null) {

            Node newNode = new Node(cur.val);

            map.put(cur, newNode);

            cur = cur.next;

        }

        //第二次遍历：通过HashMap关联各个新结点

        cur = head;

        while (cur != null) {

            map.get(cur).next = map.get(cur.next);

            map.get(cur).random = map.get(cur.random);

            cur = cur.next;

        }

        return map.get(head);

    }

}

以上题目整理来自：算法入门（go语言实现），这里给出java实现，实现思想有所不同。

巴特西

LeetCode入门指南之链表

83. 删除排序链表中的重复元素

82. 删除排序链表中的重复元素 II

206. 反转链表

92. 反转链表 II

25. K 个一组翻转链表

21. 合并两个有序链表

86. 分隔链表

147. 对链表进行插入排序

148. 排序链表

143. 重排链表

141. 环形链表

142. 环形链表 II

234. 回文链表

138. 复制带随机指针的链表

最新文章

热门文章

LeetCode入门指南 之 链表

最新文章

热门文章

LeetCode入门指南之链表