【牛客网+LeetCode】链表 OJ强训题——高效解法

今天药忘吃喽~ 2023-09-28 17:40 11阅读 0赞

**目录**

链表分割

链表回文结构

合并两个有序链表

编辑

相交链表

移除链表元素

反转链表

链表的中间结点

链表中倒数第K个结点

--------------------

# 链表分割 #

![00a702e498f74e9bb85ee47f4d016cef.png][]

> 思路：
> 
> 1.  创建两个链表（A，B）：分别创建两个头尾指针置null
> 2.  创建一个cur的指针遍历题目所给链表
> 3.  将结点值小于x的尾插入A中，否则插入B中
> 4.  判断若A段为空，返回B段头结点
> 5.  为了防止死循环，若B段存在，则有可能B段最后一个结点不为空，若不为空，则置为空
> 6.  用A链表的尾结点，连接B链表的头结点

public class Partition {
        public ListNode partition(ListNode head, int x) {
            ListNode as = null;
            ListNode ae = null;
            ListNode bs = null;
            ListNode be = null;
            ListNode cur = head;
            while(cur != null){
                //进a段
                if(cur.val < x){
                    //第一次进as
                    if(as == null){
                        as = cur;
                        ae = cur;
                    }
                    else{
                        ae.next = cur;
                        ae = cur;
                    }
                }
                else{
                    if(bs == null){
                        bs = cur;
                        be = cur;
                    }
                    else{
                        be.next = cur;
                        be = cur;
                    }
                }
                cur = cur.next;
            }
            //如果a段为空
            if(as == null){
                return bs;
            }
            //防止死循环，如果b段存在，那么有可能b段最后一个结点的不为空
            if(bs != null){
                be.next = null;
            }
            ae.next = bs;
            return as;
        }
    }

--------------------

# 链表回文结构 #

![09192a64d3ab4e13bf1e0640f58df87f.png][]

> 思路：
> 
> 1.  创建快慢指针
> 2.  通过快慢指针遍历链表
> 3.  从慢指针的next开始反转后半段链表
> 4.  最后用两指针，分别从头尾判断链表是否回文

public class PalindromeList {
        public boolean chkPalindrome(ListNode head) {
            if(head == null){
                return true;
            }
            ListNode fast = head;
            ListNode slow = head;   //快慢指针注意前后顺序，否则会引起对null指针的解引用操作
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }// 1 2  2 1
            //开始反转
            ListNode cur = slow.next;
            while(cur != null){
                ListNode curNext =cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //判断回文
            cur = head;
            while(cur != slow){
                if(cur.val != slow.val){
                    return false;
                }
                if(cur.next == slow){
                    return true;
                }
                cur = cur.next;
                slow = slow.next;
            }
            return true;
        }
    }

--------------------

# 合并两个有序链表 #

# ![71b873f27d9845e1b18740dcb7ed4c96.png][] #

> 思路：
> 
> 1.  创建一个虚拟结点
> 2.  从头开始比较两个结点value值，将较小值连接虚拟结点
> 3.  若有一个结点为空时，将该结点指向另一个结点即可
> 4.  返回虚拟结点的下一个接待

class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode newHead = new ListNode(-1);
            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;
                }
            }
            if(list1 == null){
                tmp.next = list2;
            }
            else{
                tmp.next = list1;
            }
            return newHead.next;
        }
    }

--------------------

# 相交链表 #

![6171e6b80d2b4c7cace01fb74954cabf.png][]

> 思路：
> 
> 1.  分别用两指针遍历A，B两链表，求出长度
> 2.  求长度差值，因为是Y性，所有相同结点后面的长度是一样的
> 3.  求出差值后，让长的走完这段差值，两个再同时走
> 4.  最后判断如果两指针相等，则返回相等结点

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int szA = 0;
            int szB = 0;
            ListNode curA = headA;
            ListNode curB = headB;
            //求A链表长度
            while(curA != null){
                curA = curA.next;
                szA++;
            }
            //求B链表长度
            while(curB != null){
                curB = curB.next;
                szB++;
            }
            curA = headA;
            curB = headB;
            if(szA > szB){
                //求差值，因为是Y性，所有相同结点后面的长度是一样的，所以求差值，让长的走完这段差值，两个再同时走
                int diff = szA - szB;
                while(diff != 0){
                    curA = curA.next;
                    diff--;
                }
            }
            else{
                int diff = szB - szA;
                while(diff != 0){
                    curB = curB.next;
                    diff--;
                }
            }
            while(curA != curB){
               /* if(curA == null){
                    return null;
                }*/ //判不判断无所谓，因为最后都会返回空
                curA = curA.next;
                curB = curB.next;
            }
            return curA;
        }
    }

# 移除链表元素 #

![17304e071b12469586d543a5f1d4a837.png][]

> 思路：
> 
> 1.  创建两个指针
> 2.  一个为cur用来遍历链表，找出要删除的元素
> 3.  另一个为dp指向cur上一个结点
> 4.  dp的next指向cur的next结点，同时使cur指向下一个结点，达到删除多个结点的目的

class Solution {
        public ListNode removeElements(ListNode head, int val) {
            if(head == null){
                return null;
            }
            ListNode cur = head;
            ListNode dp = cur;
            while(cur != null) {
                if (cur.val == val) {
                    dp.next = cur.next;//其实这里可以不用找前一个结点，直接插入结点，交换值即可
                    cur = dp.next;
                } else {
                    dp = cur;
                    cur = cur.next;
                }
            }
            if(head.val == val){
                head = head.next;
            }
            return head;
        }
    }

--------------------

# 反转链表 #

![3e529205e83f4bb99664c1686b3f8b28.png][]

> 思路
> 
> 1.  创建一个cur指针，指向头结点的next
> 2.  将头节点置空，作为反转后的尾结点
> 3.  创建一个curNext指针，让他始终指向cur的next
> 4.  让将head指针当作cur的上一个结点用，将head的结点的地址赋给cur的next，让cur指向curNext，curNext指向cur的next循环即可

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

--------------------

# 链表的中间结点 #

![c63e0df5c2bd4e1ba1aed47ad16ee242.png][]

> 思路：
> 
> 1.  通过快慢指针遍历链表即可
> 2.  fast指向null或者fast.next指向null的时候停下，此时慢指针便是中间结点

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

--------------------

# 链表中倒数第K个结点 #

![c820b87b0651458cbdb21c78a4b1f190.png][]

> 思路：
> 
> 1.  创建快慢指针
> 2.  让快指针先走K-1步
> 3.  再让快指针和慢指针同时向后一步一步挪动
> 4.  fast指向空时，slow指针指向的便是倒数第K个元素

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

--------------------

![22c6c3ed65ad4498b5131f31450ac21c.gif][]

[00a702e498f74e9bb85ee47f4d016cef.png]: https://img-blog.csdnimg.cn/00a702e498f74e9bb85ee47f4d016cef.png
[09192a64d3ab4e13bf1e0640f58df87f.png]: https://img-blog.csdnimg.cn/09192a64d3ab4e13bf1e0640f58df87f.png
[71b873f27d9845e1b18740dcb7ed4c96.png]: https://img-blog.csdnimg.cn/71b873f27d9845e1b18740dcb7ed4c96.png
[6171e6b80d2b4c7cace01fb74954cabf.png]: https://img-blog.csdnimg.cn/6171e6b80d2b4c7cace01fb74954cabf.png
[17304e071b12469586d543a5f1d4a837.png]: https://img-blog.csdnimg.cn/17304e071b12469586d543a5f1d4a837.png
[3e529205e83f4bb99664c1686b3f8b28.png]: https://img-blog.csdnimg.cn/3e529205e83f4bb99664c1686b3f8b28.png
[c63e0df5c2bd4e1ba1aed47ad16ee242.png]: https://img-blog.csdnimg.cn/c63e0df5c2bd4e1ba1aed47ad16ee242.png
[c820b87b0651458cbdb21c78a4b1f190.png]: https://img-blog.csdnimg.cn/c820b87b0651458cbdb21c78a4b1f190.png
[22c6c3ed65ad4498b5131f31450ac21c.gif]: https://img-blog.csdnimg.cn/22c6c3ed65ad4498b5131f31450ac21c.gif