【练习】链表题

• 🎥 个人主页：Dikz12
• 🔥个人专栏：算法(Java)
• 📕格言：吾愚多不敏，而愿加学
• 欢迎大家👍点赞✍评论⭐收藏

目录

两数相加 

题目描述 

题解 

代码实现 

两两交换链表中的节点 

题目描述 

题解

代码实现 

 重排链表

 题目描述

​编辑 题解

 代码实现

  合并 K 个升序链表

题目描述 

 题解

 代码实现

链表常用技巧 

1. 画图. -> 更加直观和形象.
2. 引入虚拟头结点.

• 更便于处理边界情况.
• 更方便对于链表的操作.

3. 快慢双指针.

• 判环
• 找链表中环的入口
• 找链表中倒数第n个结点

链表中常用操作 

1. 头插. -> 逆序链表

2. 尾插.

两数相加 

 源自leetcode的第二题，如果大家是按顺序刷题的话，可能在第二题就怀疑人生了.

题目描述 

题解 

解法：模拟两数相加过程即可. 

两个链表都是逆序存储数字的，即两个链表的个位数、⼗位数等都已经对应，可以直接相加。（如果不是逆序链表，那就需要手动逆序了） 在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。如果产⽣进 位的位置在链表尾部，即答案位数⽐原链表位数⻓⼀位，还需要再 new ⼀个结点储存最⾼位。

代码实现 

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode cur1 = l1, cur2 = l2; //指向两个链表的头节点
        ListNode newHead = new ListNode(0); //虚拟头节点
        ListNode prev = newHead; //进行尾插操作的指针
        int ret = 0; //表示进位

        while(cur1 != null || cur2 != null || ret != 0) {
            if(cur1 != null) {
                ret +=  cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null) {
                ret += cur2.val;
                cur2 = cur2.next;
            }
            prev.next = new ListNode(ret % 10);
            prev = prev.next;
            ret /= 10;
        }
        return newHead.next;
    }

两两交换链表中的节点 

题目描述 

题解

解法一: 模拟. -> 画图

解法二：递归. 

1. 递归函数的含义：交给你⼀个链表，将这个链表两两交换⼀下，然后返回交换后的头结点；
2. 函数体：先去处理⼀下第⼆个结点往后的链表，然后再把当前的两个结点交换⼀下，连接上后⾯处理后的链表；
3. 递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤交换，直接返回。

代码实现 

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode(0); // 虚拟头节点
        ListNode prev = newHead;
        ListNode cur = head;
        ListNode next = cur.next;
        ListNode nnext = next.next;
        //模拟循环过程
        while(cur != null && next != null) {
            //交换节点
            cur.next = nnext;
            next.next = cur;
            prev.next = next;
            //修改指针
            prev = cur;
            cur = nnext;
            if(cur != null) {
                next = cur.next;
            }
            if(next != null)
            nnext = next.next;
        }
        return newHead.next;
    }

递归代码： 

    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode tmp = swapPairs(head.next.next);
        ListNode cur = head.next;
        cur.next = head;
        head.next = tmp;
        return cur;
    }

 重排链表

 题目描述

 题解

1.  找中间节点；
2. 中间部分往后的逆序；
3. 合并两个链表

 代码实现

    public void reorderList(ListNode head) {
        // 特殊情况
        if(head == null || head.next == null || head.next.next == null) {
            return ;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 1.找中间节点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2.后面部分逆序(头插法)
        ListNode newHead = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null; //分割两个链表
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = curNext;
        }
        // 3.合并两个链表
        ListNode cur1 = head, cur2 = newHead.next;
        ListNode head2 = new ListNode(0);
        ListNode prev = head2;
        while(cur1 != null) {
            prev.next = cur1;
            prev = prev.next;
            cur1 = cur1.next;
            if(cur2 != null) {
                prev.next = cur2;
                prev = prev.next;
                cur2 = cur2.next;
            }
        }
    }

  合并 K 个升序链表

题目描述 

 题解

解法一： 利用优先级队列做优化. 

还有一种解法就是用递归的方式，就跟归并差不多. 

 代码实现

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

        //2.将所有的头结点放到小根堆中
        for(ListNode head : lists) {
            if(head != null) {
                heap.offer(head);
            }
        }
        //3. 合并链表
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        while(!heap.isEmpty()) {
            ListNode tmp = heap.poll();
            cur.next = tmp;
            cur = tmp;
            //把tmp的下一个节点放到小根堆中
            if(tmp.next != null) {
                heap.offer(tmp.next);
            }
        }
        return newHead.next;
    }