Leetcode 链表简单题

分手后的思念是犯贱 2023-09-29 14:14 23阅读 0赞

####  ####

*  1.合并两个有序链表
 *  2.环形链表
 *  3.相交链表(需要推导)
 *  4.移除链表元素
 *  5.链表的反转
 *  6.回文链表
 *  7.剑指 Offer 22. 链表中倒数第k个节点
 *   *  方法1 计算链表长度，根据索引找到结点
     *  方法2 快慢指针
 *  8.找到链表的中间结点

## 1.合并两个有序链表 ##

题目链接[21.合并两个有序链表][21.]  
![在这里插入图片描述][e7a17f7658f04f618ec89fe5961e23a7.png]  
思路：  
题目已经说明了给出的两个链表,A,B都是有序的，为了使得他们合并后的链表也是有序的，我们先定义一个新的链表C的头结点，我们应该定义两个指针，分别指向A链表的头结点，和B链表的头结点，对链表进行遍历，如果A链表的元素值比较小，则让C链表的头结点指向A，让后让A的指针后移，如果B链表指向的元素小，也是进行同样的操作。

注意:刚开始链表循环的条件是两个链表都非空，循环结束则说明有一个链表为空，当时我们不知道是哪一个链表为空，所以要进行判断，如果A链表为空，则让C链表的当前结点指向B链表

class Solution {
        
        public ListNode mergeTwoLists(ListNode p, ListNode q) {
        
                
                ListNode node=new ListNode();
                ListNode head=node;
                 
                while(p!=null && q!=null){
        
                    if(p.val < q.val){
        
                        node.next=p;
                        p=p.next;
                        node=node.next;
    
                        
                    }else{
        
                        node.next=q;
                        q=q.next;
                        node=node.next;
                    }
                }
               node.next= (p!=null)?p:q;
               return head.next;
        }
    }

## 2.环形链表 ##

题目链表[141 环形链表][141]  
![在这里插入图片描述][5b7d15e8a3af4615878adad6fc5f8c78.png]  
![在这里插入图片描述][f0d610834fbe430bb745973f7ab42013.png]

思路:

*  因为题目要求判断是否成环，那么如果链表为空，或者只有一个结点，都无法成环
 *  我们可以定义快慢指针，快指针移动2次，慢指针移动一次，如果链表成环，最后两个指针肯定可以相遇

/**
     使用快慢指针
      */
    public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
           if(head == null || head.next==null) return false;
           ListNode slow=head;
           ListNode fast=head.next;
           while(fast!=null && fast.next!=null){
        
               if(slow==fast) return true;
               slow=slow.next;
               fast=fast.next.next;
           }
           return false;
           
        }
    }

## 3.相交链表(需要推导) ##

题目链接:[160 相交链表][160]  
![在这里插入图片描述][a640f510a8624c9d828fd0732a260cea.png]  
![在这里插入图片描述][d3dee1f8025c48479bf30ef86a3c0b03.png]  
思路:

*  假设A链表未相交部分长度是a,相交部分长度c
 *  假设B链表未相交部分长度是b,相交部分长度是c
 *  我们分别遍历A和B，当A遍历完后，就让A指向B的头结点，B也一样的做法
 *  只要A和B的指针不相等，就不断的遍历，最后一定会相遇
 *  详细的思路大家可以看看官方提供的解题思路:[力扣官方的解题思路][Link 1]

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            //双指针
            //它们有相交的点，则说明它们的头结点都不是空
            if(headA == null || headB==null) return null;
             ListNode pA = headA, pB = headB;
            while (pA != pB) {
        
                pA = pA == null ? headB : pA.next;
                pB = pB == null ? headA : pB.next;
            }
            return pA;
    
     
        }
    }

## 4.移除链表元素 ##

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。  
![在这里插入图片描述][323e417f70464c3194b46c12744c7574.png]  
思路:  
这道题目第一眼看起来虽然简单，但是细节没有注意的话，还是会出错，我们得考虑特殊情况，如果删除的元素是头结点要怎么办呢？  
  
  
所以，我们应该先找到头结点所在位置，当头结点非空并且头结点的元素不等于val,就让指针后移，就可以得到头结点

头结点找到后，就很容易写出代码了。

class Solution {
        
        public ListNode removeElements(ListNode head, int val) {
        
             while(head!=null&&head.val==val){
        
                head=head.next;
            }        
            if(head==null) return head;
            ListNode curr=head;
            while(curr.next!=null){
                    
                if(curr.next.val==val){
                        
                    curr.next=curr.next.next;
                }else{
        
                    curr=curr.next;
                }
            }
            return head;
    
        }

## 5.链表的反转 ##

题目链接:[206 反转链表][206]  
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。  
![在这里插入图片描述][d68797c12f574f6b9423933b4a359919.png]  
![在这里插入图片描述][1230ebf7bd9c467e906812dbee5859c6.png]

思路:

*  如果头结点为null,或者链表只有一个元素，则直接返回头结点
 *  否则的话，我们定义两个指针，pre表示当前结点的前一个结点，curr表示当前结点
 *  对链表进行遍历，开始反转，指针记得变化

public ListNode reverseList(ListNode head) {
        
            if (head == null || head.next == null) return head;
            ListNode pre = null;
            ListNode curr = head;
            while (curr != null) {
        
                ListNode temp = curr.next;
                curr.next = pre;
                pre = curr;
                curr = temp;
    
            }
            return pre;
        }

## 6.回文链表 ##

题目链接:[234 回文链表][234]  
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。  
![在这里插入图片描述][f0c742898e9e4eb8bcd90af952e35050.png]  
一看到这道题目，不知道有没有小伙伴和我一样，心想，不就是先把链表反转，然后和原来的链表进行比较吗，这么简单,那么，恭喜你，和我一样都想错了。  
  
  
易错点:我们写了函数反转后，由于是引用传递，也就是链表本身会发生变化，所以不能这样做，除非有两个链表，才可以这么写。

思路分析:  
我们可以遍历链表，然后把结点的值保存在ArrayList中，然后进行回文判断

class Solution {
        
        public boolean isPalindrome(ListNode head) {
        
            List list = new ArrayList();
            ListNode p = head;
            while (p != null) {
        
                list.add(p.val);
                p = p.next;
            }
            //开始判断                   
                for (int i = 0,j=list.size()-1; i <=j; i++,j--) {
        
                    if (list.get(i)!=list.get(j)){
        
                        return false;
                    }
                }
                return true;                
        }     
       
    }

## 7.剑指 Offer 22. 链表中倒数第k个节点 ##

题目链接:[剑指 Offer 22. 链表中倒数第k个节点][Offer 22. _k]  
![在这里插入图片描述][405ac2c0bfa048299e79a69a5ceed921.png]

### 方法1 计算链表长度，根据索引找到结点 ###

*  先计算出链表长度  
    思路:
 *  然后根据索引找到对应的结点

class Solution {
        
        public ListNode getKthFromEnd(ListNode head, int k) {
        
                int len=length(head);
                ListNode p=head;
                int index=len-k;
                int cnt=0;
                while(cnt<index){
        
                    p=p.next;
                    cnt++;
                }
                return p;
        }
        //获取链表长度
        public int length(ListNode head){
        
            int i=0;
            ListNode p=head;
            while(p!=null){
        
                p=p.next;
                i++;
    
            }
            return i;
        }
    }

### 方法2 快慢指针 ###

题目要求我们找到的是倒数第k个结点，我们可以让快指针和慢指针指向的结点相差k个，那么当快指针指向链表尾部的空结点的时候，说明慢指针刚好是倒数第k个结点

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

## 8.找到链表的中间结点 ##

题目链接:[876 链表的中间结点][876]  
![在这里插入图片描述][05ba4177dbea4cbfb177a2c225275e14.png]

思路:

*  定义快慢指针
 *  快指针每次移动两个结点
 *  慢指针每次移动一个结点
 *  当快指针指向的是null,此时慢指针指向的就是中间结点

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

[21.]: https://leetcode.cn/problems/merge-two-sorted-lists/
[e7a17f7658f04f618ec89fe5961e23a7.png]: https://img-blog.csdnimg.cn/e7a17f7658f04f618ec89fe5961e23a7.png
[141]: https://leetcode.cn/problems/linked-list-cycle/
[5b7d15e8a3af4615878adad6fc5f8c78.png]: https://img-blog.csdnimg.cn/5b7d15e8a3af4615878adad6fc5f8c78.png
[f0d610834fbe430bb745973f7ab42013.png]: https://img-blog.csdnimg.cn/f0d610834fbe430bb745973f7ab42013.png
[160]: https://leetcode.cn/problems/intersection-of-two-linked-lists/
[a640f510a8624c9d828fd0732a260cea.png]: https://img-blog.csdnimg.cn/a640f510a8624c9d828fd0732a260cea.png
[d3dee1f8025c48479bf30ef86a3c0b03.png]: https://img-blog.csdnimg.cn/d3dee1f8025c48479bf30ef86a3c0b03.png
[Link 1]: https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
[323e417f70464c3194b46c12744c7574.png]: https://img-blog.csdnimg.cn/323e417f70464c3194b46c12744c7574.png
[206]: https://leetcode.cn/problems/reverse-linked-list/
[d68797c12f574f6b9423933b4a359919.png]: https://img-blog.csdnimg.cn/d68797c12f574f6b9423933b4a359919.png
[1230ebf7bd9c467e906812dbee5859c6.png]: https://img-blog.csdnimg.cn/1230ebf7bd9c467e906812dbee5859c6.png
[234]: https://leetcode.cn/problems/palindrome-linked-list/
[f0c742898e9e4eb8bcd90af952e35050.png]: https://img-blog.csdnimg.cn/f0c742898e9e4eb8bcd90af952e35050.png
[Offer 22. _k]: https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
[405ac2c0bfa048299e79a69a5ceed921.png]: https://img-blog.csdnimg.cn/405ac2c0bfa048299e79a69a5ceed921.png
[876]: https://leetcode.cn/problems/middle-of-the-linked-list/
[05ba4177dbea4cbfb177a2c225275e14.png]: https://img-blog.csdnimg.cn/05ba4177dbea4cbfb177a2c225275e14.png