小试牛刀——链表第一篇

末蓝、 2023-09-27 10:18 101阅读 0赞

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

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [java se][]  
>  我变秃了，也变强了  
> 给大家介绍一款程序员必备刷题平台——牛客网  
> [点击注册一起刷题收获大厂offer吧][offer]  
> ![在这里插入图片描述][45806c90199243eab295ada6d8239e84.png]

#### 文章目录 ####

*  一、合并两个排序的链表
 *  二、链表中倒数第k个结点
 *  三、 链表的中间结点
 *  四、 反转链表

## 一、合并两个排序的链表 ##

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。  
![在这里插入图片描述][dd037bc56704439e8c3c8e553b6562f7.png]  
![在这里插入图片描述][f7cbd4ba93384bb59daa6d2783434ddb.png]

public class Solution {
        
        public ListNode Merge(ListNode list1,ListNode list2) {
        
            ListNode newHead = new ListNode(0);
            ListNode head = newHead;
            while(list1 != null && list2 != null) {
        
                if(list1.val < list2.val) {
        
                    head.next = list1;
                    list1 = list1.next;
                    head = head.next;
                }else {
        
                    head.next = list2;
                    list2 = list2.next;
                    head = head.next;
                }
            }
            if(list1 != null) {
        
                head.next = list1;
            }else {
        
                head.next = list2;
            }
            return newHead.next;
        }
    }

## 二、链表中倒数第k个结点 ##

输入一个链表，输出该链表中倒数第k个结点。  
![在这里插入图片描述][5b781620f81543999fcae60804892a2d.png]

public class Solution {
        
        public ListNode FindKthToTail(ListNode head,int k) {
        
           if(head == null) {
        
               return null;
           }
           if(k <= 0) {
        
               return null;
           }
           ListNode fast = head;
           ListNode slow = head;
           while(k > 0) {
        
               if(fast == null) {
        
                   return null;
               }
               fast = fast.next;
               k--;
           }
           while(fast != null) {
        
               fast = fast.next;
               slow = slow.next;
           }
           return slow;
        }
    }

## 三、 链表的中间结点 ##

给定一个头结点为 head 的非空单链表，返回链表的中间结点。  
如果有两个中间结点，则返回第二个中间结点。

public ListNode middleNode(ListNode head) {
        
            ListNode fast = head;
            ListNode slow = head;
            if(head == null) {
        
                return null;
            }
            if(head.next == null) {
        
                return head;
            }
            while(fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

## 四、 反转链表 ##

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。  
![在这里插入图片描述][e4d97351297f4033a300aa086c9db1c9.png]  
![在这里插入图片描述][00a0f141e47540dd96b749294ede96d9.png]

public class Solution {
        
        public ListNode ReverseList(ListNode head) {
        
            if(head == null) {
        
                return null;
            }
            ListNode cur = head.next;
            head.next = null;
            while(cur != null) {
        
                ListNode curNext = cur.next;
                cur.next = head;
                head = cur;
                cur = curNext;
            }
            return head;
        }
    }

[b58e14a606c14e76832adc977e9ba0ba.gif_pic_center]: https://img-blog.csdnimg.cn/b58e14a606c14e76832adc977e9ba0ba.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[java se]: https://blog.csdn.net/buhuisuanfa/category_11932688.html?spm=1001.2014.3001.5482
[offer]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[45806c90199243eab295ada6d8239e84.png]: https://img-blog.csdnimg.cn/45806c90199243eab295ada6d8239e84.png
[dd037bc56704439e8c3c8e553b6562f7.png]: https://img-blog.csdnimg.cn/dd037bc56704439e8c3c8e553b6562f7.png
[f7cbd4ba93384bb59daa6d2783434ddb.png]: https://img-blog.csdnimg.cn/f7cbd4ba93384bb59daa6d2783434ddb.png
[5b781620f81543999fcae60804892a2d.png]: https://img-blog.csdnimg.cn/5b781620f81543999fcae60804892a2d.png
[e4d97351297f4033a300aa086c9db1c9.png]: https://img-blog.csdnimg.cn/e4d97351297f4033a300aa086c9db1c9.png
[00a0f141e47540dd96b749294ede96d9.png]: https://img-blog.csdnimg.cn/00a0f141e47540dd96b749294ede96d9.png