链表——数据结构

原创

延年有余 2022-06-16 20:03:27 博主文章分类：算法 ©著作权

文章标签 链表 leetcode 算法 文章分类 Java 编程语言 阅读数152

1.翻转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

1.1 递归

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head);
    }

    private ListNode reverse(ListNode head) {
        // 判断 头结点临界
        if(head == null) {
            return head;
        }
        // 判断 尾结点临界
        if(head.next == null) {
            return head;
        }
        ListNode last = reverse(head.next);
        // 翻转头结点 与 下一个节点的 next 指向
        head.next.next = head;
        // 置 头结点 的 next 为 null
        head.next = null;
        // 返回 最后 一个节点
        return last;
    }
}

1.2 双指针

class Solution {
    public ListNode reverseList(ListNode head) {
        // cur 的 前一个 节点
        ListNode prev = null;
        // 当前节点
        ListNode cur = head;
        // 保存 临时节点
        ListNode temp = null;
        while(cur != null) {
            // 保存 cur 的下一个节点
            temp = cur.next;
            // 翻转 cur 与 prev 节点的 next指向
            cur.next = prev;
            // prev 总是 cur 的前一个节点
            prev = cur;
            // cur 向前 移动 1位
            cur = temp;
        }
        return prev;
    }
}

2. 两两交换

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = []
输出：[]

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

2.1 递归

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 处理 头结点 和 尾结点 边界
        if(head == null || head.next == null) {
            return head;
        } 
        ListNode next = head.next;
        // 递归 拿到 已经 两两 交换好了的 next的 下一个节点
        ListNode newSwapNode = swapPairs(next.next);
        // 交换 head 与 next 节点 的指针指向
        next.next = head;
        // head 节点 指向 next 往后 已经 两两交换 好的 节点
        head.next = newSwapNode;
        return next;
    }
}

2.2 虚拟头结点

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 哑元节点
        ListNode dumpNode = new ListNode(0);
        dumpNode.next = head;
        // 初始化 前节点 为 哑元 节点
        ListNode prev = dumpNode;
        //  准备 两个要 交换的 节点 且保证 不能为 空
        while(head != null && head.next != null) {
            // 保存 next 的节点 的 后一个 节点
            // head 与 next 交换后 会让 前面和后面的 节点 丢失
            ListNode temp = head.next.next;
            prev.next = head.next;
            // 交换 两 节点 并 让 头结点 与 后面节点 连接
            head.next.next = head;
            head.next = temp;
            // 自变量 自增
            prev = head;
            head = head.next;
        }
        // 返回 哑元节点 的 后一个节点 即 head 节点
        return dumpNode.next;  
    }
}

3. 删除倒数第n节点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

3.1 数学

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = getLenth(head);
        // 设置 哑元 节点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        // 倒数 第 n 个 即 顺数 第 length - (n - 1) 个
        // 找到第 length - (n - 1) - 1个, 删除 它的 下一个节点
        int num  = length - (n - 1) - 1;
        ListNode prev = dummyNode;
        while(num > 0) {
            prev = prev.next;
            num -= 1;
        }
        prev.next = prev.next.next;
        return dummyNode.next;
    }
    private int getLenth(ListNode head) {
        ListNode p = head;
        int length = 0;
        while(p != null) {
            length++;
            p = p.next;
        }
        return length;
    }
}

3.2 双指针

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        // 循环 n - 1次，让 fast 比 slow 先 n - 1 个节点
        while(n > 1) {
            fast = fast.next;
            n--;
        }
        ListNode prev = null;
        while(fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next;
            slow = slow.next;
        }
        prev.next = slow.next;
        slow.next = null;
        return dummyNode.next;
    }
}

4. 链表相交

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

4.1 指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 定义 链表 A 和 B的长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // 两表长度 之差
        int dfLenAB = lenA - lenB;
        // 记录 当前 节点位置
        ListNode curA = headA;
        ListNode curB = headB;
        // A 长 B，让 较长的 遍历 直到 当前位置 到 尾结点 之间距离相同
        if(dfLenAB >= 0) {
            while(dfLenAB > 0) {
                curA = curA.next;
                dfLenAB--;
            }
        } else {
            dfLenAB = -dfLenAB;
            while(dfLenAB > 0) {
                curB = curB.next;
                dfLenAB--;
            }
        }
        // 同步 遍历，找到 一个 相同的节点 
        while(curA != null) {
            if(curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;     
        }
        // 找不到 返回 null
        return null;
    }
    private int getLength(ListNode head) {
        ListNode p = head;
        int length = 0;
        while(p != null) {
            length++;
            p = p.next;
        }
        return length;
    }
}

5. 环形链表

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

5.1 快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

二、结束语

评论区可留言，可私信，可互相交流学习，共同进步，欢迎各位给出意见或评价，本人致力于做到优质文章，希望能有幸拜读各位的建议！

专注品质，热爱生活。
交流技术，寻求同志。

—— 嗝屁小孩纸 QQ：1160886967
——其他平台： CSDN、博客园
——转发于个人博客对应链表题型

打赏
赞
收藏
评论
分享
举报

链表——数据结构_延年有余的技术博客_51CTO博客

链表——数据结构

1.翻转链表

1.1 递归

1.2 双指针

2. 两两交换

2.1 递归

2.2 虚拟头结点

3. 删除倒数第n节点

3.1 数学

3.2 双指针

4. 链表相交

4.1 指针

5. 环形链表

5.1 快慢指针

二、结束语

Recommend

Displaying Pop-Up in .NET MAUI

Travel to infinity and beyond with new Lightyear DLC in Minecraft Marketplace

龙芯发布 .NET 6 SDK 6.0.105-ea1 LoongArch64 版本 - 张善友

Gazpromneft Partners With BitRiver To Mine Bitcoin - Bitcoin Magazine

欧雷说：「有懂颤音的么？帮我纠正下？🧐」

FDA Approves Two COVID-19 Vaccines For Young Children

广汇系溢价42%拿下合金投资控股权，孙广信“买壳”筹谋资产注入？

Here’s Why It’s So Hard to Stop Robocalls | WIRED

Flutter 实现“斑马纹”背景（需要变换颜色） - 每天进步一点点OVO

小米Redmi红米K50 5G手机 2199元包邮（需用券）-聚超值

About Joyk