0


【小嘟陪你刷题05】反转链表、移除链表元素、链表的中间结点、链表中倒数第k个结点

目录

前言

此篇是小嘟对链表题的一些做题思路与实现!如果有错误的地方!请务必在评论区指出,小嘟会认真仔细的学习了!

一、反转链表

在这里插入图片描述
在这里插入图片描述

1.1 迭代

假设链表为1→2→3→∅,我们想要把它改成∅←1←2←3。
在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

在这里插入图片描述

classSolution{publicListNodereverseList(ListNode head){if(head ==null)returnnull;ListNode prev =null;ListNode cur = head;while(cur !=null){ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;}return prev;}}

在这里插入图片描述
复杂度分析:

  1. 时间复杂度:O(n),其中 nn 是链表的长度。需要遍历链表一次。
  2. 空间复杂度:O(1)。

1.2 递归

思路:用递归函数不断传入head.next,直到headnull或者heade.nextnull,到了递归最后一层的时候,让后面一个节点指向前一个节点,然后让前一个节点的next置为空,直到到达第一层,就是链表的第一个节点,每一层都返回最后一个节点。
在这里插入图片描述

classSolution{publicListNodereverseList(ListNode head){if(head ==null|| head.next ==null){return head;}ListNode newHead =reverseList(head.next);
        head.next.next = head;
        head.next =null;return newHead;}}

复杂度分析:

  1. 时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
  2. 空间复杂度:O(n),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间,最多为 n 层。

二、移除链表元素

在这里插入图片描述

2.1 迭代

在这里插入图片描述

classSolution{publicListNoderemoveElements(ListNode head,int val){if(head ==null)returnnull;ListNode prev = head;ListNode cur = head.next;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;}}

在这里插入图片描述

三、链表的中间结点

在这里插入图片描述

3.1 快慢指针

用两个指针slow与fast一起遍历链表。slow一次走一步,fast一次走两步,那么当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;
            slow = slow.next;}return slow;}}

在这里插入图片描述

四、链表中倒数第k个结点

在这里插入图片描述

4.1 快慢指针

在这里插入图片描述

publicclassSolution{publicListNodeFindKthToTail(ListNode head,int k){if(k <=0|| head ==null){returnnull;}ListNode fast = head;ListNode slow = head;while(k -1!=0){
            fast = fast.next;if(fast ==null){returnnull;}
            k--;}while(fast.next !=null){
            fast = fast.next;
            slow = slow.next;}return slow;}}

复杂度分析:

  1. 时间复杂度:O(n),不管如何,都只遍历一次单链表
  2. 空间复杂度:O(1)
标签:

本文转载自: https://blog.csdn.net/weixin_61341342/article/details/127077092
版权归原作者 摸鱼王胖嘟嘟 所有, 如有侵权,请联系我们删除。

“【小嘟陪你刷题05】反转链表、移除链表元素、链表的中间结点、链表中倒数第k个结点”的评论:

还没有评论