• 9 道经典单链表题目助你领略单链表逻辑结构的 “魅力”

    请添加图片描述

    前言：上一篇文章，我们具体讲述了链表的相关知识。本篇紧承上集，通过 9 道单链表较为 ”简单“ 的题目的讲解，让你领略单链表的别样的逻辑结构 “魅力“。同时，单链表作为笔试常考话题之一，简单题目的回顾希望能够帮助大家夯实操作单链表的基础，话不多说我们正式开始。

    tip: 由于题目都较为基础，所以尽管没有附上图解，但配合注释大家应该能够明晰


    重点：



    1 翻转链表

    206. 反转链表

    1）思路：

    （1）三指针

    • 保下引用，赋上引用，循环，返回值newHead
    • 保存下一项 curNext = cur .next ;（curNext判断，定义newHead）
    • 赋值成上一项cur .next = pre ，重定上一项 pre = cur，转向下一项cur = curNext

    （2）头插

    • cur 表示当前节点， nextCur 保存 cur 下一个节点，head 表示链表头结点
    • 从第二个节点开始遍历每个元素，进行链表头插
      • 头插过程中 先赋值 nextCur，再 cur 头插
      • 再赋值 head，cur 走向下一个元素，如此循环

    2）解法：

    • 三指针
    	public ListNode ReverseList(ListNode head) {
        
        if(head == null || head.next == null){
            return head;
        }
        
        //三指针
        ListNode preCur = null;
        ListNode cur = head;
        ListNode nextCur = null;
        
        while(cur != null){
            //保下引用
            nextCur = cur.next;
            //赋上引用
            cur.next = preCur;
            preCur = cur;
            cur = nextCur;
        }
        
        return preCur;     
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 头插
    	public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode nextCur = null;
        ListNode cur = head.next;
        head.next = null;

        while(cur != null){
            nextCur = cur.next;
            //使用 head 进行头插
            cur.next = head;
            head = cur;
            cur = nextCur;
        }

        return head;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19



    2 链表中间值

    876. 链表的中间结点

    1）思路：

    （1）快慢指针

    • 循环条件 fast != null&& fast.next != null，循环过程 fast = fast.next.next; slow = slow.next
      • 不能调换顺序，且不能使用或 否则会空指针异常
      • 奇数个，fast 停在最后一个节点，slow停在中间节点
      • 偶数个，fast 停空节点处，slow 停在中间两节点的第二个节点

    2）解法：

    • 快慢指针
    	public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;

    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12



    3 查看链表是否为回文结构

    链表的回文结构

    1）思路：

    • 找到单链表的 中间节点
    • 开始反转单链表（中间节点以后反转）
    • 一个从 头走，一个从 尾走（在 循环内部 判断 链表个数为偶数的情况，cur.next == slow）

    2）解法：

    	public boolean isPalindrome(ListNode head) {
        if(head == null) return false;

        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        //cur 到中间节点的后一个节点
        ListNode cur = slow.next;
        ListNode curNext = null;

        //开始反转
        while(cur != null){
            curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //cur 从同头开始走，slow从尾开始走
        cur = head;
        while(cur != slow){
            if(cur.val != slow.val){
                return false;
                //判断为偶数的情况
            }else if(cur.next == slow){
                break;
            }

            cur = cur.next;
            slow = slow.next;
        }

        return true;

    }

    • 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
    • 36
    • 37
    • 38
    • 39
    • 40



    4 删除排序链表中的重复元素

    1）思路：

    • 创建虚拟头结点 dummy，因为涉及链表的修改，可以省去很多特殊情况的判断

    • 从头节点开始，外循环遍历链表，找到重复的节点后，内循环 跳过可能出现的连续重复节点

      • 非重复节点的情况，pre cur 直接向后移动
      • 重复节点的情况，while 内循环cur 到达最后一个重复节点，cur = cur.next，pre.next = cur，进行跳过

    2）解法：

    	public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        
        //2 进行删除
        while(cur != null && cur.next != null){
            //    找到相同的
            if(cur.val == cur.next.val){
                //注意要判断下一个节点是否为空，本节点为空进入外循环就已经判断了
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        
        //4 返回
        return dummy.next;
    }

    • 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



    5 链表倒数第k个节点

    链表中倒数最后k个结点

    1 ) 思路:

    （1）双指针

    • 快指针 先走 k - 1 个节点
      • 可能 k 不合法, fast 每走一步判空
    • 快慢指针同时走, 直到 fast.next == null, slow就到达倒数第 k 个节点

    2 ) 解法:

    • 双指针
    	public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //快慢指针
        //1 快指针先走 k - 1
        if(pHead == null || k == 0) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        while(k > 1){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            
            k--;
        }
        
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        
        return slow;
        
        
    }

    • 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



    6 删除链表的倒数第n个节点

    删除链表的倒数第n个节点

    1 ) 思路:

    ​ ( 1 ) 双指针

    • 创建虚拟头节点 newHead, 快指针先走 n 步
      • 因为是从虚拟头节点开始走, 所以先走 n 步
    • 快慢指针同时走, 直到 fast.next == null, slow 指针走到 n - 1节点
    • slow 节点删除 n 节点, 返回 newHead.next

    ​ ( 2 ) 长度统计

    • 创建虚拟头结点
    • 遍历链表, 统计长度(加上虚拟头结点), 计算倒数 n 节点下标 nIndex
      • nIndex 下标为 链表长度 - n
    • cur 前进 nIndex - 1步, 到达删除节点的前一个节点
    • slow 节点删除 n 节点, 返回 newHead.next

    2 ) 解法:

    • 双指针
        public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here

        //解法1: 双指针
        //1 创建虚拟头节点
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        //2 快指针先走 n 步
        ListNode fast = newHead;
        ListNode slow = newHead;
        
        while(n > 0){
            fast = fast.next;
            n--;
        }
    
        //3 走快慢指针同时走, 慢指针走到n - 1节点
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        
        //4 删除节点
        slow.next = slow.next.next;
        
        return newHead.next;
        
    }

    • 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
    • 长度统计
    	public ListNode removeNthFromEnd (ListNode head, int n) {
        //解法2: 长度统计
        //1 创建虚拟头结点
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        
        //2 统计长度(加上虚拟头结点), 计算倒数 n 节点下标 nIndex
        ListNode cur = newHead;
        int size = 0;
        while(cur != null){
            size++;
            cur = cur.next;
        }
        
        int nIndex = size - n;
        //3 前进nIndex - 1步, 到达删除节点的前一个节点
        cur = newHead;
        for(int i = 0; i < nIndex -  1; i++){
            cur = cur.next;
        }
        
        //4 删除节点
        cur.next = cur.next.next;
        
        return newHead.next;
    }

    • 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



    7 重新排序并合并两个升序的链表

    21. 合并两个有序链表

    1）思路：

    • 创建虚拟头结点 newHead，cur1 cur2 遍历两链表，cur 指向新链表的尾部
    • while(cur1 cur2 != null) 遍历两链表，比较 **cur1.val 和 cur2.val，**为 cur.next 赋值，再 cur 和 cur1 / cur2 向后
    • 判断 cur1 != null 或者 cur2 != null，尾插至链表，返回 newHead.next

    2）解法：

    	public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode cur = newHead;

        //比较 cur1.val 和 cur2.val,连接到新链表
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur = cur.next;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur = cur.next;
                cur2 = cur2.next;
            }
        }

        //非空的 cur1 / cur2 直接尾插到新链表
        if (cur1 != null) {
            cur.next = cur1;
        }

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


        return newHead.next;

    }

    • 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



    8 链表分割

    链表分割

    1）思路：

    • 遍历链表， 将链表元素放在创建的链表1 (s1 e1) 链表2 (s2 e2) 中
      • 在放入的过程，要先判断头结点是否为 null，进行放入
    • 遍历结束，先判断 s1 是否为空，后判断 e2 是否为空
      • 满足 s1为空 直接返回 s2，否则 e1.next = s2 连接表1 和 表2;
      • 满足 e2 为空，让 e2.next = null，防止链表死循环

    2）解法：

    	public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode s1 = null;
        ListNode e1 = null;
        ListNode s2 = null;
        ListNode e2 = null;
        
        ListNode cur = pHead;
        
        //以 x 为基点将元素放到 s1 s2 两链表中
        while(cur != null){
            if(cur.val < x){
                //判断是否是第一次插入
                if(s1 == null){
                    s1 = cur;
                    e1 = cur;
                }else{
                    e1.next = cur;
                    e1 = cur;
                }
            }else{
                if(s2 == null){
                    s2 = cur;
                    e2 = cur;
                }else{
                    e2.next = cur;
                    e2 = cur;
                }
            }
            
            cur = cur.next;
        }
        
        //判断 s1 是否为空，为空直接将 s2 赋值给 s1
        if(s1 == null){
            s1 = s2;
         	//不为空，连接两个链表
        }else{
            e1.next = s2;
        }
        
        //判断 e2 是否为空，不为空后驱直接设置为空，防止出现死循环
        if(e2 != null){
            e2.next =null;
        }
        
        return s1;
        
        
    }

    • 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
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50



    9 求两链表的交点（Y型）

    160. 相交链表

    1）思路：

    • 求 长度，走 差值步（默认pl= headA,不满足交换：lenA
    • pl 和 ps 在同一起跑线上，向前找到相交节点

    2）解法：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }

        int lenA = 0;
        int lenB = 0;
        ListNode pl = headA;
        ListNode ps = headB;


        while(pl != null){
            lenA++;
            pl = pl.next;
        }

        while(ps != null){
            lenB++;
            ps = ps.next;
        }

        pl = headA;
        ps = headB;

    	//找到较长链表 pl，向前走差值步
        int forward = lenA - lenB;
        if(forward < 0){
            pl = headB;
            ps = headA;
            forward = - forward;
        }

        while(forward != 0){
            pl = pl.next;
            forward--;
        }

    	//pl 和 ps 同一起跑线向前找交点
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }

        return pl;

    }

    • 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
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46



    至此，文章就结束了，如果对各位小伙伴有所裨益的话，求 点赞、收藏、评论 三连，如有问题也欢迎各位看官朋友指正

    下一篇博主会更新牛客 TOP101 中关于链表的题目，点个关注不迷路哦~

  • 相关阅读:
    C. Strange Test(位运算或)
    Practical Deep Raw Image Denoisingon Mobile Devices
    统计目录下的文件数量
    谷歌云：下一代开发者和企业解决方案的强力竞争者
    华为云认证的售前工程师是什么？
    基于51单片机光照强度检测智能窗帘Proteus仿真
    python基础1
    String、StringBuffer、StringBuilder的区别
    Python test
    VUE预览PDF文件并利用pdf.js获取鼠标选中的文字和搜索，在iframe中获取选中文字，监听鼠标事件，右键菜单
  • 原文地址：https://blog.csdn.net/honglan297/article/details/126103842