单链表初阶的两道基础题

亦凉 2023-09-23 17:29 76阅读 0赞

### 初阶链表刷题 ###

*  翻转单链表（链接在末尾）
 *  链表的倒数第K个结点（链接在末尾）
 *   *  普通解法
     *  进阶解法

注意！！！

> **学习的是解题的思维！**

# 翻转单链表（链接在末尾） #

![在这里插入图片描述][022b3b4564914e3ca903ad48aebc9957.png]  
解题思路

> 如果给你一个1->2->3->4->5->null的链表，你需要将他改为5->4->3->2->1->null

**迭代解法**

我们先看图理解一下  
![在这里插入图片描述][4d942fa0a993407c89c39ed0164edfc9.png]

>  *  在第一步：我们要做的是将`cur.next`指向`prev`，但是当我的`cur.next`指向`prev`时就找不到了下一个结点。
>  *  第二步：所以我们需要再定义一个指针去存储`cur`的下一个结点`curNext=cur.next`，保存下一个结点后，我们就可以让`cur.next=prev`了，接下来呢？
>  *  第三步：我们需要做的就是让cur向右移，再让cur的next指向`1`这个结点，那么我们如何找到`1`这个结点呢？可以看到，我们的`cur.next=null`时，我们的cur正好是1这个结点，所以呢？我们就可以将cur赋值给prev:`prev=cur`,这样我们的prev就是1这个结点了（蓝框上部分）。
>  *  第四步：因为`curNext`指针存了下一个结点的地址，所以我们可以直接让`cur=curNext`,这样我们的cur就是下一个结点了，经过这个操作之后再将`curNext`置为`cur`的后一个结点，也就是`curNext=cur.next`
>  *  **最后如蓝色框上部分**

**如果还有疑问，那就看下图**  
![在这里插入图片描述][18842ee34c4b49f5b124cb16160bea62.gif_pic_center]

> 在遍历链表时，将当前节点的 `cur.next` 指针改为指向前一个节点。由于找不到前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

**代码如下**

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            //没有结点或者只有一个结点不需要逆置
            if (head==null||head.next==null) {
        
                return head;
            }
            ListNode prev=null;//记录前一个节点
            ListNode cur=head;//记录当前结点
            while (cur!=null) {
        
           	   //记录后一个结点
                ListNode curNext=cur.next;
                cur.next=prev;//当前结点的next指向前一个节点
                prev=cur;//将前一个结点移动到当前结点
                cur=curNext;//当前结点移动到下一个结点
            }
            //最后返回头节点
            return prev;
      }

**复杂度分析：**

*  时间复杂度O(n),其中 `N` 是给定链表中的结点数目。
 *  空间复杂度O(1)

# 链表的倒数第K个结点（链接在末尾） #

![在这里插入图片描述][e8b95b9b31c94675872c30928dfe0586.png]

## 普通解法 ##

> 很显然，求倒数第k个，可以转换成求正数第多少个呢？

我们来看图 ![在这里插入图片描述][25a03eb1ac2f4571974c58d0d408f717.png]

我们总共有五个结点，如果需要找到倒数第3个，那就是正数第二个，也就是正数第n-k个，n为链表长度。

>  *  第一步：遍历链表记录链表的长度
>  *  第二步：用链表长度减去k，也就是n-k,求出正数第几位
>  *  第三步：再次遍历链表，当循环n-k次后退出循环并返回

**如图：**

第一遍遍历

![在这里插入图片描述][6a4d3a565e5243539563053c4781792f.gif_pic_center]

第二遍遍历

![在这里插入图片描述][93e4263d0e1d4d0f97e2a4cfd4d62d6d.gif_pic_center]  
有了上面的过程，还需要考虑2个细节

>  *  k<=0 或者头结点最开始就为空，也就是没有节点
>  *  节点的总个数 < K

**代码如下**

public class Solution {
        
        public ListNode FindKthToTail(ListNode head,int k) {
        
        //判断链表是不是为空，并且k不能小于等于0
            if (k<=0||head==null) {
        
                return null;
            }
            int n=0;//记录链表长度
            ListNode cur=head;
            while (cur!=null) {
        
                cur=cur.next;
                n++;
            }
            //当我的链表长度小于K说明K不在链表里面
            if(n<k) {
        
                return null;
            }
            cur=head;
            int size=n-k;//循环size次
            while(size>0) {
        
                    cur=cur.next;
                    size--;
            }
            return cur;
        }

> n为链表的总长度，如果k总是在倒数第一个节点，那么此方法需要遍历链表2次，最坏时间复杂度为O(2\*n)

**复杂度分析：**

*  时间复杂度**O(2\*n)** 其中 `N` 是给定链表中的结点数目。
 *  空间复杂度**O(1)**

## 进阶解法 ##

> 定义一个快慢指针，先让快指针走K步，然后慢指针和快指针一起走，当快指针为null时，我们的慢指针就是倒数第K个数。

究竟上面的原理是如何推理出来的呢？

我们看图演示

![在这里插入图片描述][fd2bc2cd3ab8443eb563476790ed9569.png]

> 第一步：先让快指针cur走K步，如图二  
> 第二步：快指针，慢指针一起走，当快指针为null时退出循环  
> 第三步：此时prev就是倒数第K个结点，返回prev就行

具体过程如下

![在这里插入图片描述][0e5ae207ba8f40589befd94f5280c8b3.gif_pic_center]

> 使用如图的快慢指针，首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点

**代码入下**  
注意注释！！！

public class Solution {
        
        public ListNode FindKthToTail(ListNode head,int k) {
        
    		 //判断链表是不是为空，并且k不能小于等于0	
            if (k<=0||head==null) {
        
                return null;
            }
            int n=0;
            ListNode prev=head;
            ListNode cur=head;
            while (n<k) {
        
            //判断cur是否为null
            //如果为null返回null
                if (cur==null) {
        
                   return null;
                }
                cur=cur.next;
                n++;
                //如果将if放到下面，
                //那么判断倒数第n个结点时就会出错，n是链表长度，
                //也就是查找链表头节点时会报错
                //if (cur==null) {
        
                // return null;
                // }
            }
            while (cur!=null) {
        
                prev=prev.next;
                cur=cur.next;
            }
            return prev;
        }
     }

作者总结：

有一个极端条件就是当倒数第K个结点是头节点时，不能将if放到我在代码注释的那个位置，如下图  
![在这里插入图片描述][057a8e00acf34ab38fbc863570154ad4.png]

> 如果在下面判断当`cur == null`时就退出，那么存在一种情况就是当我的`cur==null`时，我的prev就是倒数第5个结点符合条件，如果此时退出结果就会和预期结果不一样，所以我们将判断的条件写在了上面，那样的话，只有当我们的n没有符合条件时并且`cur==null`，才返回null,这样就避免了上面的错误

反转一个单链表：[oj题][oj]

输入一个链表，输出该链表中倒数第k个结点[oj题][oj 1]

**下期预告：合并两个有序链表，判断回文链表，链表的相交结点**

[022b3b4564914e3ca903ad48aebc9957.png]: https://img-blog.csdnimg.cn/022b3b4564914e3ca903ad48aebc9957.png
[4d942fa0a993407c89c39ed0164edfc9.png]: https://img-blog.csdnimg.cn/4d942fa0a993407c89c39ed0164edfc9.png
[18842ee34c4b49f5b124cb16160bea62.gif_pic_center]: https://img-blog.csdnimg.cn/18842ee34c4b49f5b124cb16160bea62.gif#pic_center
[e8b95b9b31c94675872c30928dfe0586.png]: https://img-blog.csdnimg.cn/e8b95b9b31c94675872c30928dfe0586.png
[25a03eb1ac2f4571974c58d0d408f717.png]: https://img-blog.csdnimg.cn/25a03eb1ac2f4571974c58d0d408f717.png
[6a4d3a565e5243539563053c4781792f.gif_pic_center]: https://img-blog.csdnimg.cn/6a4d3a565e5243539563053c4781792f.gif#pic_center
[93e4263d0e1d4d0f97e2a4cfd4d62d6d.gif_pic_center]: https://img-blog.csdnimg.cn/93e4263d0e1d4d0f97e2a4cfd4d62d6d.gif#pic_center
[fd2bc2cd3ab8443eb563476790ed9569.png]: https://img-blog.csdnimg.cn/fd2bc2cd3ab8443eb563476790ed9569.png
[0e5ae207ba8f40589befd94f5280c8b3.gif_pic_center]: https://img-blog.csdnimg.cn/0e5ae207ba8f40589befd94f5280c8b3.gif#pic_center
[057a8e00acf34ab38fbc863570154ad4.png]: https://img-blog.csdnimg.cn/057a8e00acf34ab38fbc863570154ad4.png
[oj]: https://leetcode.cn/problems/reverse-linked-list/submissions/386749185/
[oj 1]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking