算法系列--链表刷题(二)

💕"轻舟已过万重山"💕
作者：Mylvzi
文章主要内容：算法系列–链表刷题(二)

今天为大家带来的是算法系列--链表刷题(二),带来了几道经典的有关链表的面试题(合并K个有序列表)

1.两数相加

https://leetcode.cn/problems/add-two-numbers/

模拟两数相加:

使用两个指针cur1和cur2来遍历两个链表,通过t记录每次相加的结果,最后创建出新的节点,尾插

注意:

每次相加时都需要更新t的值,但是不可以直接将t设置为0,因为存在进位的可能,比如t = 9 + 9 = 18,要插入节点的val = 8,还要记录进位1,所以:val = t % 10, t /= 10
循环的结束要同时满足三个条件,cur1 = null, cur2 = null, t = 0,其中最后t = 0这种情况最容易忘记,导致最后需要进位没进位成,结果相比于正确答案少了一位
代码:

/**
 * 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 phead = new ListNode(0);
        ListNode cur = phead;// 用于尾插

        int t = 0;// 用于表示本次相加的结果  处理进位

        // 要注意t最后可能不为0 要进一位
        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;
            }

            ListNode newNode = new ListNode(t % 10);
            t /= 10;

            // 尾插
            cur.next = newNode;
            cur = newNode;
        }
        return phead.next;
    }
}

2.两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

思路:

分别得到下标为奇数的所有节点的组合和下标为偶数的所有节点的组合(下标从1开始)
按照偶数节点在前,奇数节点在后的顺序合并两个链表
得到新的链表

代码实现:

/**
 * 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 swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        // 定义两个虚拟节点 分别接收奇数和偶数的节点
        ListNode p1 = new ListNode(0);
        ListNode p2 = new ListNode(0);

        ListNode cur1 = p1;
        ListNode cur2 = p2;

        ListNode cur = head;
        int i = 1;

        // 分别得到奇数和偶数的链表组合
        while(cur != null) {
            ListNode newNode = new ListNode(cur.val);

            if(i % 2 != 0) {
                // 奇数
                cur1.next = newNode;
                cur1 = newNode;
            }else {
                // 偶数
                cur2.next = newNode;
                cur2 = newNode;
            }

            cur = cur.next;
            i++;
        }

        // 合并两个链表
        ListNode p3 = new ListNode(0);
        ListNode t1 = p1.next;
        ListNode t2 = p2.next;
        ListNode cur3 = p3;

        while(t1 != null || t2 != null) {
            if(t2 != null) {
                cur3.next =  t2;
                cur3 = t2;
                t2 = t2.next;
            }

            if(t1 != null) {
                cur3.next =  t1;
                cur3 = t1;
                t1 = t1.next;
            }
        }

        return p3.next;
    }
}

注:本题更加简洁的写法是通过递归实现的,感兴趣的可以去我的算法系列里查看

3.重排链表

https://leetcode.cn/problems/reorder-list/

思路:

首先获得中间节点,以中间节点为基准,分为两个不同的链表l1和l2
逆序l2
合并两个链表

在这里插入图片描述

代码:

/**
 * 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 void reorderList(ListNode head) {
        ListNode slow = head, fast = head;

        // 找到中间节点
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode l1 = head;
        ListNode l2 = slow.next;
        slow.next = null;

        // 逆序第二个节点
        l2 = reverseList(l2);

        ListNode phead = new ListNode(0);
        ListNode cur = phead;

        // 合并两个链表
        while(l1 != null || l2 != null) {
            if(l1 != null) {
                cur.next = l1;
                cur = l1;
                l1 = l1.next;
            }
            if(l2 != null) {
                cur.next = l2;
                cur = l2;
                l2 = l2.next;
            }
        }

        head = phead.next;

    }

    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;

        ListNode pHead = new ListNode(0);

        ListNode cur = head;

        while(cur != null) {
            ListNode curNext = cur.next;
            
            cur.next = pHead.next;
            pHead.next = cur;

            cur = curNext;
        }
        return pHead.next;
    }
}

同样的本题也有更加简洁的递归写法

4.合并 K 个升序链表（hard）

链接:
https://leetcode.cn/problems/merge-k-sorted-lists/description/

分析:

思路一:利用优先级队列

其实本题和合并两个有序链表很相似,可以看做是上一题的plus版本

虽然这里是合并K个有序链表,但是我们可以借鉴合并两个有序链表的思路,`创建一个傀儡节点,找到两个链表节点的最小值,依次插入到傀儡节点之后

这里的难点在于如果只有两个节点,我们可以直接比较,但是现在有K个节点,如何快速地找到K个节点的最小值呢?使用优先级队列,利用优先级队列将K个链表的头结点存入到优先级队列之中,由于默认是小根堆,所以堆顶元素就是K个链表头结点的最大值,将其插入到傀儡节点之后,更新傀儡节点,然后插入堆顶节点的下一个节点,接着判断最小值,重复上述过程

手写:
在这里插入图片描述
代码:

/**
 * 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 mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((o1,o2) ->o1.val - o2.val);
        ListNode ret = new ListNode(0);
        ListNode phead = ret;


        for(ListNode head : lists)// 将链表的头结点存入堆中
            if(head != null)
                heap.offer(head);

        while(!heap.isEmpty()) {
            ListNode tmp = heap.poll();
            phead.next = tmp;
            phead = tmp;

            if(tmp.next != null) heap.offer(tmp.next);// 注意下一个节点可能为空
        }

        return ret.next;
    }
}

思路二:利用归并的思想

其实这道题非常符合分治归并的思想,题目相当于给了我们一个比较特殊的数组(数组的元素是链表),实际上最重要完成的工作就是对这K个元素进行从小到大的排序,既然是排序我们就可以使用归并的思想,为什么想到归并呢?这是经过分析得到的,实际上我们是对一个一个的链表进行合并+排序操作的,这一步其实就是归并中分解到最小单元,开始回并的过程啊!所以可以使用归并的思想解决

代码:

/**
 * 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 mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        // 采用归并的思想解决
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left,int right) {
        // 递归出口
        if(left >= right) return lists[left];

        int mid = (left + right) /2;
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid + 1,right);

        return mergeTwoLists(l1,l2);
    }

    // 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 递归
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}

5.K个⼀组翻转链表

链接:
https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

分析:

本题采用模拟的思想,具体的模拟策略如下:

求出要反转多少个长度为K的链表–n
翻转n次即可

在这里插入图片描述
代码:

/**
 * 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 reverseKGroup(ListNode head, int k) {
        // 求需要翻转的组数n
        int cnt = 0;
        ListNode tmp = head;
        while(tmp != null) {
            cnt++;
            tmp = tmp.next;
        }

        int n = cnt / k;

        // 开始进行翻转
        ListNode ret = new ListNode(0);
        ListNode phead = ret;
        ListNode cur = head;
        for(int i = 0; i < n; i++) {
            ListNode prev = cur;// 保存当前翻转链表的头结点
            for(int j = 0; j < k; j++) {
                ListNode curnext = cur.next;
                cur.next = phead.next;
                phead.next = cur;
                cur = curnext;
            }
            phead = prev;// 每翻转完一组就更新phead
        }

        phead.next = cur;

        return ret.next;
    }
}