0


【LeetCode】简单链表题

文章目录

提示:以下是本篇文章正文内容,下面案例可供参考

1.LeetCode203移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
删除结点的步骤:
1.找到该结点的前一个结点
2.进行删除操作
3.最后处理头结点也为要删除结点的操作
题解:

classSolution{publicListNoderemoveElements(ListNode head,int val){//防止链表为空if(head ==null)returnnull;ListNode prev = head;//prev作为要删除的前一个结点ListNode cur = head.next;//cur作为要删除的结点while(cur !=null){if(cur.val == val){//此时为要删除的情况
                prev.next = cur.next;
                cur = cur.next;}else{//不删除的情况
                prev = cur;
                cur = cur.next;}}//最后处理头结点if(head.val == val){
            head = head.next;}return head;}}

2.LeetCode206反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
在遍历链表时,将当前结点的next 指针改为指向前一个结点。由于结点没有引用其前一个结点,所以我们必须先存储其前一个结点。在更改引用之前,还需要存储后一个结点。最后返回新的头引用。
在这里我们申请prev为一个结点,最初指向null申请cur存储头结点

classSolution{publicListNodereverseList(ListNode head){if(head==null){returnnull;}ListNode prev =null;ListNode cur = head;while(cur !=null){//记录当前结点的下一个节点ListNodeCurNext=cur.next;//然后将当前结点指向prev
              cur.next= prev;//prev和cur结点都前进一位
              prev = cur;
              cur=CurNext;}return prev;}}

3.LeetCode876链表的中间结点

给定一个 头结点为 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
对于这道题,我们可以采用双指针来解决,用两个指针 slow (慢指针)
fast(快指针) 一起遍历链表。slow 一次走一步,fast 一次走两步。fast速度是slow的2倍,所以路程也是2倍,那么当 fast 到达链表的末尾时,slow 必然位于中间(奇数位与中间,偶数位于第二个中间结点)。

题解:

classSolution{publicListNodemiddleNode(ListNode head){//预防链表为空的情况if(head ==null){returnnull;}ListNode fast = head;ListNode slow = head;while(fast!=null&& fast.next!=null){
         fast = fast.next.next;//fast走两步
         slow = slow.next;//slow走一步}return slow;}}

4.LeetCode21合并两个有序链表

解题步骤:
1.先申请一个虚拟结点,并且让tmp遍历链表
2.分别比较list1、list2数据大小
3.比完之后肯定有一个链表没被合并完,有一个链表已经合并完成。我们直接将链表末尾指向未合并完的链表即可
题解:

classSolution{publicListNodemergeTwoLists(ListNode list1,ListNode list2){ListNode newHead =newListNode(0);//先申请虚拟结点ListNode tmp = newHead;while(list1!=null&& list2!=null){if(list1.val < list2.val){
               tmp.next = list1;
               list1 = list1.next;
               tmp = tmp.next;}else{
               tmp.next = list2;
               list2 = list2.next;
               tmp = tmp.next;}}//并后list1和list2最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表if(list1==null){
           tmp.next = list2;}else{
        tmp.next = list1;}return newHead.next;}}

总结

提示:以上就是关于链表的简单题

🌟Hello world 我们下期见!

标签: 链表 leetcode list

本文转载自: https://blog.csdn.net/lsh0414/article/details/125340455
版权归原作者 Dream_辉辉 所有, 如有侵权,请联系我们删除。

“【LeetCode】简单链表题”的评论:

还没有评论