首页 > 其他分享 >牛客剑指offer刷题链表篇

牛客剑指offer刷题链表篇

时间:2023-11-01 14:34:02浏览次数:35  
标签:head ListNode next 链表 牛客 null 节点 刷题

@[TOC]

从尾到头打印链表

题目

输入一个链表的头节点,从尾到头反过来打印出每个节点的值。

思路

利用栈后进先出的性质实现;

代码实现
private static void printReverseNode(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode pNode = head;
        Stack<ListNode> stack = new Stack<>();
        while (pNode != null) {
            stack.add(pNode);
            pNode = pNode.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop().value);
        }
    }

    private static class ListNode {
        public ListNode next;
        public int value;

        public ListNode(int value) {
            this.value = value;
        }
    }

反转链表

题目

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

思路

遍历各个节点,修改指针指向前一节点实现,需要定义两个变量记录前一节点以及当前节点;

代码实现
/**
     * 反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //前一节点
        ListNode prev = null;
        //当前节点
        ListNode current = null;
        while (head != null) {
            //取出当前节点
            current = head;
            //移动到下一个节点
            head = head.next;
            //当前界面的next指向前一节点
            current.next = prev;
            //赋值给前一节点
            prev = current;
        }
        return prev;
    }

合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路

从头依次比较各个节点大小,哪个链表当前节点小,则取出当前节点,移动到下一个节点处,继续递归比较得到最终结果;

代码实现
private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode result = null;
        if (list1.value < list2.value) {
            result = list1;
            result.next = mergeTwoLists(list1.next, list2);
        } else {
            result = list2;
            result.next = mergeTwoLists(list1, list2.next);
        }
        return result;
    }

两个链表的第一个共同结点

题目

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

思路

由题目可知,当存在共同结点时,结构如下:

牛客剑指offer刷题链表篇_代码实现

则首先需要计算两条链表的长度得到长度差,而从将链表移动到相同长度位置,然后同时遍历两条链表,则第一个相同节点即为所求节点;

代码实现
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int headALength = getListNodeLength(headA);
        int headBLength = getListNodeLength(headB);
        ListNode currentA = headA;
        ListNode currentB = headB;
        if (headALength > headBLength) {
            // headA 移动到相同长度位置
            int num = headALength - headBLength;
            for (int i = 0; i < num; i++) {
                currentA = currentA.next;
            }
        } else {
            int num = headBLength - headALength;
            for (int i = 0; i < num; i++) {
                currentB = currentB.next;
            }
        }
        while (currentA != null && currentB != null) {
            if (currentA == currentB) {
                return currentA;
            } else {
                currentA = currentA.next;
                currentB = currentB.next;
            }
        }
        return null;

    }


    private static int getListNodeLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

链表中环的入口结点

题目

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

牛客剑指offer刷题链表篇_链表_02

思路
  1. 首先使用快慢指针移动得到环上相遇节点;
  2. 然后将快指针移动到头节点处;
  3. 同时移动快慢指针,一次移动一步,再次相遇即为入环节点;
代码实现
public static ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head.next;
        if (fast == null) {
            return null;
        }
        fast = fast.next;
        if (fast == null) {
            return null;
        }
        ListNode slow = head.next;
        while (fast != slow) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

链表中倒数第K个节点

题目

实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。

示例:

输入: 1->2->3->4->5 和 k = 2输出: 4 说明:

给定的 k 保证是有效的。

思路
  1. 倒数第k个节点,假设链表有n个节点,则从头节点出发应该走n-k+1步;
  2. 若正向走则需要两次遍历,一次得到链表长度,然后在从头走n-k+1步;
  3. 可以定义2个指针,第一个指针先走k-1步,第二个指针再和第一个指针同时走,当第一个指针到达尾节点时,此时第二个指针到达位置即为所求节点【因为此时第二个指针走的步数正好为n-(k-1)步】。
public static int kthToLast(ListNode head, int k) {
        if (head == null || k < 1) {
            return Integer.MIN_VALUE;
        }
        ListNode first = head;
        for (int i = 0; i < k - 1; i++) {
            if (first.next != null) {
                first = first.next;
            } else {
                return Integer.MIN_VALUE;
            }
        }
        ListNode result = head;
        while (first.next != null) {
            first = first.next;
            result = result.next;
        }
        return result.val;
    }

复杂链表的复制

题目

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

思路1【时间复杂度和空间复杂度均为O(n)】

利用HashMap依次复制各个节点进行存储,然后再次遍历设置next以及random节点;

实现代码1
public static Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //声明一个map用于存储<节点,节点>映射关系
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
思路2【直接复制链表】
  1. 首先对每个节点进行拷贝,并拼接到各个对应节点后面,如1->2->3 变成 1->1'->2->2'->3->3';
  2. 将拷贝节点对应的random指针添加上;
  3. 分离拷贝节点以及原始节点,最终拆分为1->2->3 和1'->2'->3';
代码实现2
public static Node copyRandomList2(Node head) {
        if (head == null) {
            return head;
        }
        //1.将拷贝节点放到原节点后面,例如1->2->3的链表变成 1->1'->2->2'->3->3'
        for (Node node = head, copyNode = null; node != null; node = node.next) {
            copyNode = new Node(node.val);
            copyNode.next = node.next;
            node.next = copyNode;
        }
        //2.将拷贝节点的random指针添加上
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }
        //3.分离拷贝节点和原节点,变成1->2->3和1'->2'->3'两个链表,返回后一个链表
        Node newHead = head.next;
        for (Node node = head, copy = null; node != null && node.next != null; ) {
            copy = node.next;
            node.next = copy.next;
            node = copy;
        }
        return newHead;
    }

删除链表中的重复结点

题目

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

思路

新建虚拟结点插入头结点,依次遍历各个节点比较值,如果一致,则跳过当前节点;

代码实现
public static ListNode deleteDuplicates(ListNode head) {
        ListNode result = new ListNode();
        result.next = head;
        ListNode temp = result;
        while (temp.next != null && temp.next.next != null) {
            if (temp.next.val == temp.next.next.val) {
                int value = temp.next.val;
                while (temp.next != null && temp.next.val == value) {
                    temp.next = temp.next.next;
                }
            } else {
                temp = temp.next;
            }
        }
        return result.next;
    }

删除链表的节点

题目

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/

代码实现
public ListNode deleteNode(ListNode head, int val) {
         ListNode result = new ListNode(Integer.MIN_VALUE);
        result.next = head;
        ListNode cur = result;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return result.next;
    }

标签:head,ListNode,next,链表,牛客,null,节点,刷题
From: https://blog.51cto.com/u_16335954/8122139

相关文章

  • 《安富莱嵌入式周报》第320期:键盘敲击声解码, 军工级boot设计,开源CNC运动控制器,C语言
     视频版:https://www.bilibili.com/video/BV1Cr4y1d7Mp/1、键盘敲击声解码https://arxiv.org/abs/2308.01074键盘敲击声被解码的话,我们使用键盘输入密码将被方便的解码出来。这篇文章介绍了一种使用最先进的深度学习模型,以便使用手机麦克风对笔记本电脑敲击键盘分析。实际测试训练......
  • 刷题笔记——哈希表(C)
    215.数组中的第K个最大元素-力扣(LeetCode)给定整数数组nums和整数k,请返回数组中第**k**个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。解题思路哈希+开放定址法注......
  • 【刷题日记】其二
    2023.10.30星期一晚上有场div.2,刷刷思维题17:21R1400思维T00:25:41https://codeforces.com/problemset/problem/1605/C最后还是看题解了,自己做一直WA2,原来少了一种情况反正就是最少的时候,只有两个a相邻和三个a相邻的情况,都枚举一遍就行代码#include<bits/stdc++.h>usin......
  • 两种方式讲链表节点删除
    第一种讲法就是循环的方式,因为要循环遍历这个链表,所以我们会运用到一个很重要的哨兵思想,就是定一个没啥意义的哨兵,让head“makesense”,接着,我们的任务是对链表进行删除,那就涉及到一个前端链表的指向问题,但是现在这个是单向链表,我们无法知道你前面那个是谁,所以我们也可以想办法......
  • 141. 环形链表
    目录题目法一、快慢指针法二、哈希表题目给你一个链表的头节点head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。注意:po......
  • 234.回文链表
    目录题目法一、复制+反转链表法二、堆栈法三、快慢指针和链表反转题目给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false法一、复制+反转链表把原......
  • 05数据结构(栈、队列、数组、链表)
    数据结构一、什么是数据结构计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。数据结构是为了更加方便的管理和使用数据,需要结合具体的业务场景来进行选择。一般情况下,精心选择的数据结构可以带来更高的运行或者存储效率。如何学习数据结构:每......
  • 21. 合并两个有序链表
    目录题目代码题目将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输出:[0]代码class......
  • 面试必刷TOP101:16、删除有序链表中重复的元素-II
    一、题目二、题解importjava.util.*;publicclassSolution{publicListNodedeleteDuplicates(ListNodehead){//空链表if(head==null)returnnull;ListNoderes=newListNode(0);//在链表前加一个表头......
  • 19. 删除链表的倒数第 N 个结点(中)
    目录题目法一、循环法二、快慢指针题目给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:输入:head=[1,2],n=1输出:[1]法一、循环classSolution:......