力扣--链表算法_力扣链表数据类型的方法

一、删除中间点

内容

实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。

示例

输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val; //将下一节点的值赋给当前节点
        node.next = node.next.next; //当前节点的下一个节点为下下节点，删除当前节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度

时间复杂度：O(1)。
空间复杂度：O(1)。

二、二进制链表转整数

内容

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 。

示例

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

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        ListNode cur = head;  
        int ans = 0;
        while(cur != null){
            //链表只有0/1
            ans = ans * 2 + cur.val;
            cur = cur.next;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度

时间复杂度：O(N)，其中N是链表中的节点个数。
空间复杂度：O(1)。

三、返回倒数第K个节点

内容

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例

输入： 1->2->3->4->5 和 k = 2
输出： 4

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        if(k <= 0 || head == null){
            return 0;
        }
        ListNode fast = head;
        ListNode slow = head;
        //让快指针先快走K-1步
        while(k - 1 > 0){ 
            fast = fast.next;
            k--;
        }
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow.val;
    }
}
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

复杂度

时间复杂度 O(N) :N为链表长度。
空间复杂度 O(1)。

四、从尾到头打印链表

内容

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例

输入：head = [1,3,2]
输出：[2,3,1]

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
    //使用栈，先进后出原则
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode node = head;
        while(node != null){
            stack.push(node);
            node = node.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for(int i = 0;i < size;i++){
            print[i] = stack.pop().val;
        }
        return print;
    }
}
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

复杂度

时间复杂度：O(n)正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。
空间复杂度：O(n)额外使用一个栈存储链表中的每个节点。

五、链表的中间结点

内容

给定一个头结点为 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.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度

时间复杂度：O(N)O(N)，其中 NN 是给定链表的结点数目。
空间复杂度：O(1)O(1)，只需要常数空间存放 slow 和 fast 两个指针。

六、移除重复节点

内容

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null){
            return head;
        }
        //HashSet特点无序不可重复
        Set<Integer> occurred = new HashSet<Integer>();
        //先将头节点的值加进哈希表中
        occurred.add(head.val);
        ListNode pos = head;
        while(pos.next != null){
            ListNode cur = pos.next;
            if(occurred.add(cur.val)){
                pos = pos.next;
            }else{
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }
}
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

复杂度

时间复杂度：O(N)，其中 N 是给定链表中节点的数目。
空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N 个值。

七、反转链表

内容

反转一个单链表。

示例

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

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。

八、合并两个有序链表

内容

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

示例

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else{
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        //合并后l1和l2最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.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

复杂度

时间复杂度：O(n + m)O(n+m) ，其中 nn 和 mm 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)O(n+m)。

空间复杂度：O(1)O(1) 。我们只需要常数的空间存放若干变量。

九、链表相交

内容

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例

输入：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 个节点。

代码

/**
 * 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) {
        ListNode t1 = headA;
        ListNode t2 = headB;
        while(t1 != t2){
            t1 = t1 != null ? t1.next : headB;
            t2 = t2 != null ? t2.next : headA;
        }
        return t2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度

十、链表中的下一个更大节点

内容

给出一个以头节点 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 。

示例

输入：[2,1,5]
输出：[5,5,0]

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
      int[] arr = new int[10000]; //给定列表的长度在 [0, 10000] 范围内
        int[] valueArr = new int[10000];    //给定列表的长度在 [0, 10000] 范围内
        Stack<Integer> stack = new Stack<>();   

        int length = 0;
        int value;

        while(head != null){
            value = head.val;   
            valueArr[length] = value;   
            while(!stack.isEmpty() && value > valueArr[stack.peek()]){  //栈不为空，且当前值大于前几位
                arr[stack.pop()] = value;  //将大值放入arr数组中
            }
            stack.add(length);  //栈放坐标
            length++;
            head = head.next;
        }
        int[] result = new int[length]; //遍历数组放入result
        for(int i = 0;i < length; i++){
            result[i] = arr[i];
        }
        return result;
    }
}
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

复杂度

十一、两数相加

内容

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头

示例

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

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //定义头尾节点为null
       ListNode head = null;
       ListNode tail = null;
       //进位
       int carry = 0;
       while(l1 != null || l2 != null){
           int n1 = l1 != null ? l1.val : 0;
           int n2 = l2 != null ? l2.val : 0;
           int sum = n1 + n2 + carry;
           if(head == null){
               //首尾在同一位置
               head = tail = new ListNode(sum % 10);
           }else{
               //尾节点后移
               tail.next = new ListNode(sum % 10);
               tail = tail.next;
           }
           //进位最大为1，如9+9=18
           carry = sum > 9 ? 1 : 0;
           if(l1 != null){
               l1 = l1.next;
           }
           if(l2 != null){
               l2 = l2.next;
           }
       }
       //如果最后还有进位尾节点下一位为1
       if(carry > 0){
           tail.next = new ListNode(carry);
       }
       return head;
    }
}
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

复杂度

时间复杂度：O(max(m,n))，其中m和n分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)的时间。
空间复杂度：O(1)。注意返回值不计入空间复杂度。

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度

内容

示例

代码

复杂度