链表 算法专题

链表算法题技巧

1. 画图!
2. 引入虚拟"头"结点
   便于处理边界情况
   方便我们对链表操作
3. 不要吝啬空间, 大量去定义变量

链表中的常见操作

1. 创建一个新的节点
2. 尾插
3. 头插(逆序链表)

一. 两数相加

两数相加

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode newHead = new ListNode(0);//创建一个虚拟头结点, 记录结果
        ListNode tail = newHead;//记录每次尾插的位置
        int t = 0;  //将想家的结果放在t中
        while(cur1 != null || cur2 != null || t != 0){//有进位也要继续算
            if(cur1 != null){
                t += cur1.val;
            cur1 = cur1.next;
            }
            if(cur2 != null){
                t += cur2.val;
            cur2 = cur2.next;
            }
            tail.next = new ListNode(t % 10);//取个位
            tail = tail.next;
            t /= 10;//取进位, 加到下一次的结果中
        }
        return newHead.next;
    }
}

二. 两两交换列表中的结点

两两交换列表中的结点

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode prev = newHead;
        ListNode cur1 = head;
        ListNode cur2 = head.next;
        ListNode tail = cur2.next;

        while(cur1 != null && cur2 != null){
            prev.next = cur2;
            cur2.next = cur1;
            cur1.next = tail;

            prev = cur1;
            cur1 = tail;
            if(cur1 != null) cur2 = cur1.next;
            if(cur2 != null) tail = cur2.next;

        }
        return newHead.next;
    }
}

三. 重排链表

重排链表

class Solution {
    public void reorderList(ListNode head) {
        // 1. 找到链表的中间结点, 将链表一分为二
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 将后半链表逆序, 头插法
        ListNode cur = slow.next;
        slow.next = null;// 将前后链表分离
        ListNode head2 = new ListNode(0);
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        // 3. 将两个链表合并
        ListNode cur1 = head;
        ListNode cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while (cur1 != null) {

            prev.next = cur1;
            cur1 = cur1.next;
            prev = prev.next;
            if (cur2 != null) {
                prev.next = cur2;
                cur2 = cur2.next;
                prev = prev.next;
            }

        }
    }
}

四. 合并k个升序链表

合并k个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //1. 创建一个小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        //2. 把所有的头结点放在小根堆中
        for(ListNode head : lists){
            if(head != null){
                heap.offer(head);
            }
        }

        //3. 合并链表
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(!heap.isEmpty()){
            ListNode t = heap.poll();
            prev.next = t;
            prev = prev.next;
            if(t.next != null){
                heap.offer(t.next);
            }
        }

        return ret.next;
    }
}