当前位置:   article > 正文

Leetcode链表刷题思路汇总

Leetcode链表刷题思路汇总

链表

链表相关的题,最快的入门方法就是做题的时候画图。标注A的next节点是哪里,单链表的遍历只能是单向的,从头结点到尾结点。

例如:给你一个链表的head头,让你返回最后元素的值
if (head == null) {
	return -1;
}
while (head.next != null) {
	head = head.next;
}
return head.val;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

最近花了大概一个月的时间,将链表的专题刷完了,记录总结一下,题怎么刷比较容易理解,常规套路还有一些题的题解。

一些常规套路

1、对于大部分链表的题,我们都需要一个哑结点,就是在头结点之前再创建一个节点并将哑结点的next指向head,这样处理会帮助我们解决边界问题。

2、链表题基本都是对next指针的调整,而不是值本身。

3、对于删除来说就是找前驱,一般会用到快慢双指针。(例如第19题,删除倒数第n个节点)

4、一般来说我们要返回的和过程中处理的是两个引用,因为过程中处理的需要不断的cur = cur.next。而返回时要返回头结点。

5、对于改next指针的时候注意不要路径覆盖,否则会导致死循环。例如(Q24交换链表节点)

6、对于找链表中位数,就是快慢指针,快指针一次移动两次,慢指针一次移动一次。

7、关于环、快慢指针,当fast==slow时证明有环,此时head和slow边移动边比较,相等时就是入环的点。

算法
1、两数之和(2)

题目:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
  • 1
  • 2
  • 3

链接:https://leetcode-cn.com/problems/add-two-numbers

思路:将两个链表当前节点值(当前链表为null,值就是0)相加并加上进位,进位初始化为0,然后创建新的链表对象,新的对象的val为结果%10;然后如果两个链表哪个不为null就往后遍历。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        //  cur 作为不断变化的指针
        ListNode cur = new ListNode(0);
        //  res 指向cur后不再变化
        ListNode res = cur;
        while (l1!=null || l2!=null){
            int a1 = l1!=null?l1.val:0;
            int a2 = l2!=null?l2.val:0;
            int sum = a1+a2+add;
            add = sum / 10;
            // cur next开始存的是真正的结果
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1!=null){
                l1 = l1.next;
            }
            if (l2!=null){
                l2 = l2.next;
            }
        }
        if (add > 0){
            cur.next = new ListNode(add);
        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
2、删除倒数第n个链表

题目:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

**进阶:**你能尝试使用一趟扫描实现吗?

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
  • 1
  • 2

思路:哑结点,快慢指针,慢指针指向哑结点,快指针走n步后,快慢一起走。slow.next = slow.next.next移除。

public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        // 添加哑结点
        ListNode res = new ListNode(0,head);
        // slow 和 res指向同一个地址
        ListNode slow = res;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
3、合并两个升序链表(21)

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

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
  • 1
  • 2

思路:判断A>B就创建个新的往结果加,最后A,B哪个不为空再加到最后。

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 使用哑结点免去头结点判断代码
        ListNode cur = new ListNode(0);
        // res是真正从头到尾的链表,cur是控制当前节点动的。
        ListNode res = cur;
        while (l1!=null && l2!=null){
            if (l1.val<=l2.val){
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            }else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1!=null){
            cur.next = l1;
        }
        if (l2!=null){
            cur.next = l2;
        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
4、合并K个升序链表(23)

题目:给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

思路:归并排序

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

    public ListNode mergeList(ListNode[] lists,int head,int tail){
        if (head == tail){
            return lists[head];
        }
        if (head > tail){
            return null;
        }
        int mid = (head+tail)/2;
        return merge(mergeList(lists,head,mid),mergeList(lists,mid+1,tail));
    }

    private ListNode merge (ListNode l1,ListNode l2){
        ListNode res = new ListNode(-1);
        ListNode ans = res;
        while (l1!=null && l2!=null){
            if (l1.val <= l2.val){
                res.next = l1;
                l1 = l1.next;
            }else {
                res.next = l2;
                l2 = l2.next;
            }
            res = res.next;
        }
        if (l1!=null){
            res.next = l1;
        }
        if (l2!=null){
            res.next = l2;
        }
        return ans.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
5、两两交换链表中的节点(24)

题目:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

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

输入:head = [1,2,3,4]
输出:[2,1,4,3]
  • 1
  • 2

思路:利用哑结点,设置next next.next 节点转换,循环就行了,注意的是cur一下跳两个节点

    public static ListNode swapPairs(ListNode head) {
        ListNode cur = new ListNode(-1);
        cur.next = head;
        ListNode res = cur;
        while (cur.next!=null && cur.next.next!=null){
            ListNode tmp1 = cur.next;
            ListNode tmp2 = cur.next.next;
            tmp1.next = tmp2.next;
            tmp2.next = tmp1;
            cur.next = tmp2;
            cur = cur.next.next;
        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
6、K 个一组翻转链表(25)

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

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

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

进阶:

你可以设计一个只使用常数额外空间的算法来解决此问题吗?
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
  • 1
  • 2

思路:每k个链表反转,最后拼到一起就行了

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int len = 0;
        List<ListNode> all = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            len++;
            if (len == k) {
                len = 0;
                ListNode next = cur.next;
                cur.next = null;
                all.add(head);
                head = next;
                cur = next;
            } else {
                cur = cur.next;
            }
        }
        return reverse(all, head);
    }

    public ListNode reverse(List<ListNode> heads, ListNode end) {
        ListNode res = new ListNode(-1);
        ListNode ans = res;
        for (ListNode head : heads) {
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            res.next = pre;
            while (res.next!=null){
                res = res.next;
            }
        }
        res.next = end;
        return ans.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
7、旋转链表(61)

题目:给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
  • 1
  • 2

思路:将链表连成环,然后移动,然后再将环拆开,

public static ListNode rotateRight(ListNode head, int k) {
        // 只有头节点是null的时候需要特殊处理一下
        if (head == null) {
            return null;
        }
        ListNode low = head;
        ListNode fast = head;
        int len = 1;
        while (fast!=null){
            if (fast.next == null){
                // 到链表最后一个节点了,此时将链表连成一个环
                fast.next = head;
                break;
            }
            fast = fast.next;
            len++;
        }
        k = k%len;
        int loop = len-k;
        //  len-k代表的是移动方向几次low指向头结点,画图能看出来端倪
        while (loop > 0){
            low = low.next;
            fast = fast.next;
            loop--;
        }
        fast.next=null;
        return low;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
8、删除排序链表中的重复元素 II(82)

题目:存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
  • 1
  • 2

思路:找当前的节点和后继节点比较,值一样,while判断后面还有没有一样的,一样的全去掉。如果当前和后继不一样就往后移动一位

public static ListNode deleteDuplicates(ListNode head) {
       ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur.next!=null && cur.next.next!=null){
            if (cur.next.val == cur.next.next.val){
                int x = cur.next.val;
                while (cur.next!=null && x == cur.next.val){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return res.next;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
9、删除排序链表中的重复元素(83)

题目:存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次

返回同样按升序排列的结果链表。

输入:head = [1,1,2]
输出:[1,2]
  • 1
  • 2

思路:下一个跟当前相同,就把下一个删了。

public static ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        ListNode res = cur;
        while (cur!=null && cur.next!=null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
10、分隔链表(86)

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

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

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
  • 1
  • 2

思路:创建大小两个链表,遍历一遍将大小分开组装,然后大小链表拼起来就行了

public static ListNode partition(ListNode head, int x) {
        ListNode cur = head;
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        ListNode res = small;
        ListNode tmpBig = big;
        while (cur!=null){
            if (cur.val<x){
                small.next = new ListNode(cur.val);
                small = small.next;
            }else {
                big.next = new ListNode(cur.val);
                big = big.next;
            }
            cur = cur.next;
        }
        small.next = tmpBig.next;
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
11、反转链表 II(92)

题目:给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
在这里插入图片描述

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]
  • 1
  • 2

思路:穿针引线把经过的节点放到最前面这样经过[left,right]部分就是反转的了,头插法。先找到pre

public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        int tmpLeft = left;
        while (left > 1) {
            left--;
            pre = pre.next;
        }
        ListNode cur = pre.next;
        int tmp = right - tmpLeft;
        ListNode cNext;
        while (tmp > 0) {
            tmp--;
            cNext = cur.next;
            cur.next = cNext.next;
            cNext.next = pre.next;
            pre.next = cNext;

        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
12、有序链表转换二叉搜索树(109)

题目:给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

       0
      / \
    -3   9
   /   /
 -10  5
  • 1
  • 2
  • 3
  • 4
  • 5

思路:这个就是前序遍历建树就行了。恢复成BST 不断的找中位数,因为链表是有序的,递归时每次把中间的数加为节点进行构造二叉树就可以了

public TreeNode sortedListToBST(ListNode head) {
        return createNode(head, null);
    }

    TreeNode createNode(ListNode head, ListNode tail) {
        // 当头==尾时,说明当前节点下面没有子树了。
        if (head == tail) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = createNode(head, slow);
        root.right = createNode(slow.next, tail);
        return root;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
13、复制带随机指针的链表(138)

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

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
  • 1
  • 2

思路:先复制一份node,A-A’-B-B’-C-C’这样,然后每个节点的random再复制,副本的random等于原random的next;最后再将其拆开。

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        Node old = head;
        Node newNode = head.next;
        Node res = head.next;
        while (newNode != null) {
            old.next = old.next.next;
            newNode.next = newNode.next == null ? null : newNode.next.next;
            // 往尾部挂节点
            old = old.next;
            newNode = newNode.next;
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
14、环形链表(141)

题目:给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

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

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
  • 1
  • 2
  • 3

思路:快慢指针,如果快慢指针相等代表有环

public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
15、环形链表 II(142)

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

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
  • 1
  • 2
  • 3

思路:快慢指针相等确定有环,然后再用头结点和慢指针一步一步遍历相等的点就是入环的点。

public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                // 有环
                ListNode pre = head;
                while (pre!=slow){
                    pre = pre.next;
                    slow = slow.next;
                }
                return pre;
            }
        }
        return null;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
16、重排链表(143)

题目:给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…

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

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
  • 1

思路:快慢指针找到中点,然后将后面的反转,中断前后,最后遍历前后拼接进来。

public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode reverse = mid.next;
        mid.next = null;
        ListNode pre = null;
        while (reverse!=null){
            ListNode next = reverse.next;
            reverse.next = pre;
            pre = reverse;
            reverse = next;
        }
        while (head!=null && pre!=null){
            ListNode h1 = head.next;
            ListNode p1 = pre.next;
            head.next = pre;
            head = h1;
            pre.next = head;
            pre = p1;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
17、对链表进行插入排序(147)

题目:对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。

插入排序算法:

插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。

输入: 4->2->1->3
输出: 1->2->3->4
  • 1
  • 2

思路:插入排序,每次从前到后遍历确定插入的位置。

   public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode moved = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (moved.val <= cur.val) {
                moved = moved.next;
                cur = cur.next;
            } else {
                ListNode prev = pre;
                while (prev.next.val <= cur.val){
                    prev = prev.next;
                }
                // 将链接上,把cur节点去掉,接上后面的
                moved.next = cur.next;
                // cur节点移动到前面位置
                cur.next = prev.next;
                prev.next = cur;
                cur = moved.next;
            }
        }
        return pre.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
18、排序链表(148)

题目:给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

输入:head = [4,2,1,3]
输出:[1,2,3,4]
  • 1
  • 2

思路:归并排序,注意尾tail作为末位判断

    public ListNode sortList(ListNode head) {
        return sort(head,null);
    }

    public ListNode sort(ListNode head,ListNode tail){
        // 当头==尾时,说明当前节点下面没有子树了。
        if (head == tail){
            return head;
        }
        // 找中点,然后合并,类似构建二叉树
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=tail && fast.next!=tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode next = mid.next;
        mid.next = null;
        ListNode left = sort(head, mid);
        ListNode right = sort(next, tail);
        return merge(left, right);
    }

    /**
     * 合并两个升序链表
     * @param l1
     * @param l2
     */
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (l1!=null && l2!=null){
            if (l1.val >= l2.val){
                cur.next = l2;
                l2 = l2.next;
            }else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        if (l1!=null){
            cur.next = l1;
        }
        if (l2!=null){
            cur.next = l2;
        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
19、相交链表(160)

题目:编写一个程序,找到两个单链表相交的起始节点。

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

思路:a+b = b+a

/**
     * 解题思路:
     * a1->a2->c1->c2->c3->b1->b2->b3->c1->c2->c3;
     * b1->b2->b3->c1->c2->c3->a1->a2->c1->c2->c3;
     * --------------------------------!-----------
     * a+b 和 b+a 如果有重合的那么肯定最后的几个元素就是重合的元素、 上面就是!处的c1是重复的
     *
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
20、移除链表元素(203)

题目:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
  • 1
  • 2

思路:遍历,相等就删除

    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return null;
        }
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur!=null && cur.next!=null){
            ListNode next = cur.next;
            if (next.val == val){
                cur.next = next.next;
            }else {
                cur = cur.next;
            }
        }
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
21、反转链表(206)

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
  • 1
  • 2

思路:反转链表

    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next= pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
22、回文链表(234)

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

输入: 1->2->2->1
输出: true
  • 1
  • 2

思路:先找中点,然后反转后面,然后遍历对比都相等,则是回文。

public static boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return result;
    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private static ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // next和next.next能保证偶数链表中点出现在前面  1-2-3-4  2的位置  而 fast  fast.next的方式中点会出现在3的位置需要额外判断
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
23、删除链表中的节点(237)

题目:请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点

输入:head = [4,5,1,9], node = 5
输出:[4,1,9]
解释:给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
  • 1
  • 2
  • 3

思路:当前节点值是下一个节点的值,然后把下一个节点删除,这样就能达到效果了。

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
  • 1
  • 2
  • 3
  • 4
24、奇偶链表(328)

题目:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

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

思路:双节点,奇数节点和偶数节点。穿针引线。

public ListNode oddEvenList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode odd = head;
        ListNode res = odd;
        ListNode even = head.next;
        ListNode evenTmp = even;
        while (even !=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenTmp;
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
25、430. 扁平化多级双向链表(430)

题目:多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。

给你位于列表第一级的头节点,请你扁平化列表,使所有结点出现在单级双链表中。

输入:head = [1,2,null,3]
输出:[1,3,2]
解释:

输入的多级列表如下图所示:

  1---2---NULL
  |
  3---NULL
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思路:这个就是广度优先遍历,使用Deque 队列。但是有个小坑,就是是一个双链表,要把结果的child置空,prev指向前驱。

public Node flatten(Node head) {
        if (head == null){
            return null;
        }
        Deque<Node> stack = new ArrayDeque<>();
        Node res = new Node(-1);
        Node ans = res;
        stack.push(head);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            if (pop.next!=null){
                stack.push(pop.next);
            }
            if (pop.child!=null){
                stack.push(pop.child);
            }
            // 指前后节点,child置空
            pop.next = null;
            pop.child = null;
            res.next = pop;
            pop.prev = res;
            res = res.next;
        }
        ans = ans.next;
        ans.prev = null;
        return ans;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
26、两数相加 II(445)

题目:给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
  • 1
  • 2

思路:这个需要遍历到尾,然后再加,再加就像两数相加一样。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2!=null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode cur = null;
        int add = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || add !=0){
            int a = stack1.isEmpty()?0:stack1.poll();
            int b = stack2.isEmpty()?0:stack2.poll();

            int sum = a+b+add;
            add = sum / 10;
            ListNode node = new ListNode(sum%10);
            node.next = cur;
            cur = node;
        }
        return cur;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
27、设计链表(707)

题目:设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

思路,类中定义一个链表,维护链表的数据

class MyLinkedList {
    ListNode head;
    int size;
    public MyLinkedList() {
        head = new ListNode(-1);
        size = 0;
    }
    public int get(int index) {
        if (index <0 ||  index>=size){
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.next.val;
    }
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    public void addAtIndex(int index, int val) {
        if (index < 0 ){
            index = 0;
        }
        if (index > size){
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index<0 || index>=size){
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
28、分隔链表(725)

题目:给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例: 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表,而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

思路:先分每个段几个元素然后从头往后遍历,将对应的元素放到返回数组里。

    public static ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        if (root == null){
            return res;
        }
        int[] arr = new int[k];
        ListNode loop = root;
        int len = 0;
        while (loop!=null){
            len++;
            loop = loop.next;
        }
        // 分配每个段几个元素
        for (int i = 0; i < len; i++) {
            arr[i%k]++;
        }
        ListNode cur = root;
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            ListNode nowNode = new ListNode(-1);
            nowNode.next = cur;
            ListNode tmpNode = nowNode;
            while (cur!=null && tmp>0){
                tmp--;
                cur = cur.next;
                tmpNode = tmpNode.next;
            }
            tmpNode.next = null;
            res[i] = nowNode.next;
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
29、链表组件(817)

题目:给定链表头结点 head,该链表上的每个结点都有一个 唯一的整型值 。

同时给定列表 G,该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 G 中)构成的集合。

输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的,且 G 中不包含 2,所以 [0, 1] 是 G 的一个组件,同理 [3] 也是一个组件,故返回 2。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

思路:当前节点在G中出现且next节点在G中没出现就是组件的次数,G中所有的元素能构成多少个head中相连的子链表?

public int numComponents(ListNode head, int[] G) {
        if (head == null){
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < G.length; i++) {
            map.put(G[i],null);
        }
        int res = 0;
        ListNode cur = head;
        while (cur!=null){
            if (map.containsKey(cur.val) && (cur.next==null||!map.containsKey(cur.next.val))){
                res++;
            }
            cur = cur.next;
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
30、链表的中间结点(876)

题目:给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
  • 1
  • 2
  • 3
  • 4
  • 5

思路:快慢双指针找中点。

    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
31、 链表中的下一个更大节点(1019)

题目:给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node_1, node_2, node_3, … 。

每个节点都可能有下一个更大值(next larger value):对于 node_i,如果其 next_larger(node_i) 是 node_j.val,那么就有 j > i 且 node_j.val > node_i.val,而 j 是可能的选项中最小的那个。如果不存在这样的 j,那么下一个更大值为 0 。

返回整数答案数组 answer,其中 answer[i] = next_larger(node_{i+1}) 。

注意:在下面的示例中,诸如 [2,1,5] 这样的输入(不是输出)是链表的序列化表示,其头节点的值为 2,第二个节点值为 1,第三个节点值为 5 。

输入:[1,7,5,1,9,2,5,1]
输出:[7,9,9,9,0,5,0,0]
  • 1
  • 2

思路:求解下一个更大的值,这种就是用单调栈。1下一个比1大的是7,5下一个比它大的是9如果没有比自己大的就是0

    public int[] nextLargerNodes(ListNode head) {
        if (head == null){
            return new int[]{0};
        }
        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < list.size(); i++) {
            // 4,1,7,3,5
            while (!stack.isEmpty() && list.get(stack.peek())<list.get(i)){
                // 栈不为空,栈顶小于当前值。 栈里是 4,1 当前是7 那么1出栈(1在数组中的索引是1),设置1的索引对应的下一个最大值为7。
                // 继续循环,栈里是4,当前是7 那么4出栈(4在数组中的索引是0),设置0的索引对应的下一个最大值为7然后栈空或者下一个栈顶值小于7打破循环
                // 如果没有更大值就是默认值的0,如果数组是  9,1,7,3,5 那么9肯定不会出栈,9的索引0也不会被赋值
                Integer index = stack.pop();
                res[index] = list.get(i);
            }
            stack.push(i);
        }
        return res;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
new Stack
for(遍历处理数组){
    while(栈非空 && 达到预期条件){ // 一般预期条件是栈顶 < 当前位置的值
        出栈并处理,保存到结果集
    }
    入栈(栈中保存数组的索引)
}
while(栈非空){   // 如果这道题就不需要这步了。因为不存在是0,0就是int的默认值
    出栈处理剩余栈内元素
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
32、从链表中删去总和值为零的连续节点(1171)

题目:给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。

删除完毕后,请你返回最终结果链表的头节点。(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。
  • 1
  • 2
  • 3

思路:需要两遍遍历,第一次遍历构建一个map,map的key是遍历过程中的sum和,value为遍历过程中的list. 第二次遍历,如果get(sum)能取到,就证明cur和get取出来的列表之间的和是0;那么cur.next = get.next;

public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> map = new HashMap<>();

        // 首次遍历建立 节点处链表和<->节点 哈希表
        // 若同一和出现多次会覆盖,即记录该sum出现的最后一次节点
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }

        // 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }

        return dummy.next;
     }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
33、二进制链表转整数(1290)

题目:给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)
  • 1
  • 2
  • 3

思路:先反转,然后遍历链表,过程中记录要乘的基数。 按照2进制进行乘 加 就行了

    public int getDecimalValue(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        int loop = 1;
        int sum = 0;
        while (pre != null) {
            sum += pre.val * loop;
            pre = pre.next;
            loop *= 2;
        }
        return sum;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
34、二叉树中的列表(1367)

题目:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True ,否则返回 False 。

一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。

输入:head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出:true
解释:树中蓝色的节点构成了与链表对应的子路径。
  • 1
  • 2
  • 3

思路:前序遍历树,然后head作为每个树节点的参照物。

public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null){
            return true;
        }
        if (root == null){
            return false;
        }
        return sub(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }

    private boolean sub(ListNode head, TreeNode root){
        if (head == null){
            return true;
        }
        if (root == null){
            return false;
        }
        if (head.val != root.val){
            return false;
        }
        return sub(head.next,root.left) || sub(head.next,root.right);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
35、合并两个链表(1669)

题目:给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。

请你将 list1 中第 a 个节点到第 b 个节点删除,并将list2 接在被删除节点的位置。

输入:list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出:[0,1,2,1000000,1000001,1000002,5]
解释:我们删除 list1 中第三和第四个节点,并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
  • 1
  • 2
  • 3

思路:删list1 然后记录断点,list2遍历到尾,将其拼接上就行

public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode res = new ListNode(0);
        res.next = list1;
        ListNode cur = res;
        for (int i = 1; i < a; i++) {
            cur = cur.next;
        }
        ListNode pre = cur;
        int move = b-a;
        while (move >=0 && cur != null){
            move--;
            cur = cur.next;
        }
        pre.next = list2;
        ListNode cur2 = list2;
        while (cur2!=null && cur2.next!=null){
            cur2 = cur2.next;
        }
        cur2.next = cur.next;
        return res.next;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
36、交换链表中的节点(1721)

题目:给你链表的头节点 head 和一个整数 k

交换 链表正数第 k 个节点和倒数第 k 个节点的值后,返回链表的头节点(链表 从 1 开始索引)。

输入:head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出:[7,9,6,6,8,7,3,0,9,5]
  • 1
  • 2

思路:找到对应节点,然后换值、

    public ListNode swapNodes(ListNode head, int k) {
        if (head == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }
        ListNode node1 = fast;
        while (fast!=null && fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        int tmp = node1.val;
        node1.val = slow.val;
        slow.val = tmp;
        return head;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

以上:剩下的剑指offer和面试题都是重复的题了、

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/659420
推荐阅读
相关标签
  

闽ICP备14008679号