自学内容网 自学内容网

【练习】链表题

  • 🎥 个人主页: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 个升序链表

题目描述 

 题解

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

把所有的头结点放进⼀个⼩根堆中,这样就能快速的找到每次 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;
    }

原文地址:https://blog.csdn.net/m0_65465009/article/details/140566648

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!