147. 对链表进行插入排序

Problem: 147. 对链表进行插入排序

思路

  • 维护有序链表,开始时只有一个头节点。
  • 哑节点dommuy.next = head，便于在头节点前插入节点
  • 有序链表最后一个节点lastSorted
  • 待插入节点cur
  • while循环对cur遍历
    • 如果lastSorted <= cur,将lastSorted和cur均向后移动一个节点
    • 否则，需要将cur插入到有序链表中。定义prev为有序链表中cur节点的邻近前节点。初始化prev为哑节点（不是头节点，要用prev.next比较）。
      • 如果prev的后节点小于等于cur，prev向后移动一位
      • 否则。说明找到了插入位置，改变lastSorted，cur，prev的next指针，将cur插入到有序链表中。
    • 将cur更新为lastSorted.next

Code

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

        ListNode dommuy = new ListNode(0);
        dommuy.next = head;
        ListNode lastSorted = head;
        ListNode cur = head.next;
        while(cur != null){
            if(lastSorted.val <= cur.val){
                lastSorted = lastSorted.next;
            }else{
                ListNode prev = dommuy;//不是head，头节点也要比较
                while(prev.next.val <= cur.val){
                    prev = prev.next;
                }
                lastSorted.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            cur = lastSorted.next;
        }

        return dommuy.next;
    }
}

160. 相交链表

Problem: 160. 相交链表

思路

https://blog.csdn.net/qq_46724069/article/details/123818453
相同节点：地址和值都相等。

  • 先将链表A中的元素存入HashSet。
  • 遍历B中的每个节点，如果找到地址和值均相同的节点，说明此节点为相交节点，返回次节点；如果暂时没找到，则比较下一个节点。
  • 如果直到链表B末尾还没找到相交节点，返回null。

复杂度

  • 时间复杂度:$O(m+n)$，其中$m$和$n$分别是链表$A$和链表$B$的长度。两个链表均需遍历一次。
  • 空间复杂度:$O(m)$，其中$m$是链表$A$的长度，需要将链表$A$中的全部节点存入哈希集合中。

Code

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
/**
 * 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) {
        Set<ListNode> set = new HashSet<>();
        ListNode tmpA = headA;
        while(tmpA != null){
            set.add(tmpA);
            tmpA = tmpA.next;
        }
        ListNode tmpB = headB;
        while(tmpB != null){
            if(set.contains(tmpB)){
                return tmpB;
            }
            tmpB = tmpB.next;
        }
        return null;
    }
}

206. 反转链表

Problem: 206. 反转链表

思路

1 -> 2 -> 3 -> 4 -> 5 -> null 反转后为 5 -> 4 -> 3 -> 2 -> 1 -> null <=> null <- 1 <- 2 <- 3 <- 4 <- 5

  • 当前节点cur，初始化为head
  • 前一个节点pre，初始化时表示原链表末尾
  • 暂存下一个节点tmp
  • 循环：
    • 将当前节点指向前一个节点
    • 暂存当前节点到pre
    • 访问下一个节点
  • 返回pre

复杂度

  • 时间复杂度: $O(n)$，遍历链表使用线性大小时间。
  • 空间复杂度: $O(1)$，变量 pre 和 cur 使用常数大小额外空间

Code

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