首页 > 其他分享 >链表补充题目

链表补充题目

时间：2023-07-08 13:36:34浏览次数：32  
标签：head 题目 cur 补充 next 链表 ListNode null 

package SecondBrush.LinkedList;
/**
 * 83. 删除排序链表中的重复元素
 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
 * */
/**
 * 这个题目自己就直接做出来了，只是循环条件少写了一个 cur.next != null
 * 首先这道题目是 排序链表，所以相等的一定在一起，只需要对比 cur.val 和 cur.next.val
 * 如果相等直接跨过去，
 * 不相等就直接 移动 指向
 * */

public class RemoveDuplicatesSortedList_83 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return head;
    }

}
package SecondBrush.LinkedList;
/**
 * 82. 删除排序链表中的重复元素 II
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 * */
/**
 * 想到的方法是双指针,因为这个可能设计到删除头结点，所以需要使用虚拟头结点
 * 简单梳理思路：因为涉及到删除元素，所以需要虚拟头节点，双指针，一个指向虚拟节点（prev），一个指向 head（cur），
 * 因为要删除重复元素，且是有序的，所以重复元素都是在一起的，所以使用cur找到最后一个重复元素
 * 如果pre.next 是cur，说明两个指针之间没有重复数据，否则 pre.next = cur.next
 * */

public class RemoveDuplicatesSortedListII_82 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummynode = new ListNode(-1,head);
        ListNode prev = dummynode;
        ListNode cur = head;
        while (cur!= null){
            //如果出现重复的情况如下
            //相等的结点则跳过,走到相同值元素的最后一步
            while (cur.next!=null && cur.val == cur.next.val){
                cur = cur.next;
            }
            //如果pre和cur之间没有重复节点，pre后移
            if (prev.next == cur){
                prev = prev.next;
            }else {
                prev.next = cur.next;
            }
            cur = cur.next;
        }
        return dummynode.next;
    }
}
package SecondBrush.LinkedList;
/**
 * 92. 反转链表 II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * */
/**
 * 自己尝试写一下，将中间链表单独拿出来反转，之后，再进行拼接
 *
 *
 * */
public class ReverseLinkedListII_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}
package SecondBrush.LinkedList;
/**
 * 876. 链表的中间结点
 * 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * */
/**
 * 1.朴素解法：先遍历整个链表，得到长度，再取中间值，然后再遍历一半取目标值
 *
 * 2.快慢指针：没想到这个，有点环形链表的意思
 * */
public class MiddleLinkedList_876 {
    public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
    }
}
package SecondBrush.LinkedList;
/**
 * 剑指 Offer 22. 链表中倒数第k个节点
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 * */
/**
 * 1.朴素解法：想到的就是先遍历长度，然后减去 倒数长度，从前往后走
 * 2.快慢指针：这个和之前的有一道题目很像，
 * */
public class GetKthFromEnd_22 {

    public ListNode getKthFromEnd(ListNode head, int k) {
        int len = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            len++;
        }
        cur = head;
        int cha = len - k;
        for (int i = 0; i < cha; i++) {
            cur = cur.next;
        }
        return cur.next;
    }

    public ListNode getKthFromEnd2(ListNode head, int k) {

        ListNode frontNode = head, behindNode = head;
        while (frontNode != null && k > 0) {

            frontNode = frontNode.next;
            k--;
        }

        while (frontNode != null) {

            frontNode = frontNode.next;
            behindNode = behindNode.next;
        }

        return behindNode;
    }

}
package SecondBrush.LinkedList;
/**
 * 234. 回文链表
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 回文链表指的是有对称性
 * */
/**
 * 找到最后的节点，一个朝前遍历，一个朝后遍历，判断相遇前是否全部一致，如果不一致，说明不是回文链表
 * -- 初始想法，但是写不出来，后指针不好往前遍历
 *
 * 现在想起来快慢指针
 *
 * */
public class PalindromeLinkedList_234 {
    public boolean isPalindrome(ListNode head) {
        // 要实现 O(n) 的时间复杂度和 O(1) 的空间复杂度，需要翻转后半部分
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 根据快慢指针，找到中间节点或者前半部分链表的尾节点（注意判断条件）
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反转后半部分链表
        slow = reverse(slow.next);
        while(slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     * 反转（迭代）
     */
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode next = null;
        while(head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}
package SecondBrush.LinkedList;
/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * */
/**
 * 思路：初始想法，定义两个指向，分别指向两个链表的头结点，然后谁小，就排在前面
 *
 * */
public class MergeTwoSortedLists_21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 类似归并排序中的合并过程
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        // 任一为空，直接连接另一条链表
        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }
        return dummyHead.next;
    }
}
package SecondBrush.LinkedList;
/**
 * 面试题 02.04. 分割链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你不需要保留每个分区中各节点的初始相对位置。
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * */
/**
 * 初始想法，首先要找到，第一个大于或等于x的节点，这个直接遍历即可--
 *
 * 想的不太对
 * */
public class PartitionListLCCI_0204 {

    public ListNode partition(ListNode head, int x) {
            ListNode small = new ListNode(0);
            ListNode smallHead = small;
            ListNode large = new ListNode(0);
            ListNode largeHead = large;
            while (head != null) {
                if (head.val < x) {
                    small.next = head;
                    small = small.next;
                } else {
                    large.next = head;
                    large = large.next;
                }
                head = head.next;
            }
            large.next = null;
            small.next = largeHead.next;
            return smallHead.next;
        }

}
package SecondBrush.LinkedList;
/**
 * 141. 环形链表
 *给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 * */
public class LinkedListCycle_141 {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
}
package SecondBrush.LinkedList;

/**
 * 剑指 Offer 06. 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 */


public class PrintLinkedList_offer06 {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        int[] nums = new int[count];
        cur = head;
        for (int i = count - 1; i >= 0; i--) {
            nums[i] = cur.val;
            cur = cur.next;
        }
        return nums;
    }
}
package SecondBrush.LinkedList;
/**
 * 剑指 Offer 35. 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
 * 还有一个 random 指针指向链表中的任意节点或者 null。
 * */
public class CopyRandomList_offer35 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2->2'->3->3'
        for (Node node = head, copy = null; node != null; node = node.next.next) {
            copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }
        //把拷贝节点的random指针安排上
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }
        //分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        Node newHead = head.next;
        for (Node node = head, temp = null; node != null && node.next != null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }

        return newHead;
    }
}

 

标签：head,题目,cur,补充,next,链表,ListNode,null
From： https://www.cnblogs.com/lipinbigdata/p/17537086.html

相关文章

  • C语言：数据结构之单链表（二）
    上一篇随笔谈了谈单链表是什么东西，然后进行了初始化，这篇随笔就开始对其进行操作了，首先是增，删，改，查的增。增，顾名思义就是要增加新的元素，单链表是链式的，那就要考虑怎么去加新元素，有三种，从头部添加，从尾部添加，从中间添加。先说说从尾部添加，这个比较好理解，直接在尾部放一个结点......
  • 2021年电赛题目基于互联网的摄像测量系统（D题）
    基于互联网的摄像测量系统设计报告2021年全国大学生电子设计竞赛试题<10cmO拍摄方向θ1mx1m拍摄方向BA边长为1米的正方形测试区域l互联网参赛注意事项(1)11月4日8:00竞赛正式开始。本科组参赛队只能在【本科组】题目中任选一题；高职高专组参赛队在【高职高专组】题目中任......
  • 那些神奇的转化到坐标或网格上的题目
    [AGC002E]CandyPiles[AGC015E]Mr.AokiIncubator......
  • 【17.0】前端基础jQuery之jQuery补充
    【17.0】前端基础jQuery之jQuery补充【一】组织标签后续执行方式一<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><scriptsrc="https://cdn.bootcdn.net/ajax/libs/jque......
  • 【暑假题目】20030703 两数相加
    两数相加题目请使用C++计算出2^2023与3^2023的和题目分析首先通过题目，我们将所求的两个加数看为a,b，我们可以关注到两个点：1.首先要解决的是两个加数的求法，这里分别有两种求法：①通过for循环求得a,b两个加数。②通过指数函数pow函数得到a,b两个加数。在可以调用函数的情况下......
  • 淘宝技术三面题目：分布式架构+红黑树+SpringMVC+设计模式
     淘宝一面Java容器有哪些？哪些是同步容器,哪些是并发容器？ArrayList和LinkedList的插入和访问的时间复杂度？java反射原理，注解原理？新生代分为几个区？使用什么算法进行垃圾回收？为什么使用这个算法？HashMap在什么情况下会扩容，或者有哪些操作会导致扩容？HashMappush方法的执行过......
  • js 异步 任务 题目解析（chatgpt bug了？）
    最近遇到一道题如下，求输出结果感觉还是蛮有意思的，找chatgpt做了一下我是题asyncfunctionasync1(){console.log('1');awaitasync2();console.log('2');}asyncfunctionasync2(){console.log('3');}console.log('4')setTimeout(func......
  • LeetCode 160. 相交链表
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){......
  • 12.9 链表 - 综合汇总----???
    demo本章节综合汇总信息，在这个demo都可以体现----看的有点懵～！！～interfaceILink<E>{ //链表公共标准 /** *向链表中进行数据的存储，每个链表所保存的数据类型相同，不允许保存null数据 *@parame要保存的数据 */ publicvoidadd(Ee); /** *获取链表中集合......
  • Java源码系列4——HashMap扩容时究竟对链表和红黑树做了什么?
    Photobyhippopx.com我们知道HashMap的底层是由数组，链表，红黑树组成的，在HashMap做扩容操作时，除了把数组容量扩大为原来的两倍外，还会对所有元素重新计算hash值，因为长度扩大以后，hash值也随之改变。如果是简单的Node对象，只需要重新计算下标放进去就可以了，如果是链表和红黑......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99