【力扣/牛客刷题】链表篇

xxxflower

发布于 2023-04-16 17:44:35

20400

代码可运行

文章被收录于专栏：《数据结构》《数据结构》

运行总次数：0

代码可运行

203.移除链表元素

题目OJ链接：203. 移除链表元素

【题目分析】我们先来分析一下我们需要注意什么

链表为空
链表中只有一个数字
所要删除的数字位于链表中间（即最普通的情况）
链表中要寻找的数字从头开始出现多次（例如：23 23 23 45 23）（删除23）

我们先设置两个值：

cur:代表当前需要删除的节点
prev:代表当前需要删除的节点的前驱

我们要怎么删除34呢？步骤如下：

如果不是所要求的值，则执行else往后走。直到cur == null 综上我们可以得到代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //1. 链表为空
        if(head == null){
            return null;
        }
        //2. 所要删除的数字位于链表中间（即最普通的情况）
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        //3. 链表中要寻找的数字从头开始出现多次（例如：23 23 23 45  23）（删除23）此时以上代码执行完时，还有第一个没有删除，因此需要在判断一下
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

206.反转链表

题目OJ链接：206. 反转链表

【题目分析】

先把0x89存起来，方便之后与后续链表产生关系 ListNode cur = head.next;
然后将0x89置为空 head.next = null;
由以下代码得：

此处的代码为本题的关键，如果还不理解可以调试一下，一步步走。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //1.没有节点
        if(head == null){
            return null;
        }
        //2.只有一个节点
        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;
    }
}

876. 链表的中间结点

题目OJ链接：876.链表的中间结点

【题目分析】本题可以利用快慢指针来完成。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while((fast != null)&&(fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

链表中倒数第k个结点

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
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--;
        }
        while(fast.next != null){
            fast = fast.next; 
            slow = slow.next;
        }
        return slow;

    }
}

21. 合并两个有序链表

思路：定义一个虚拟头结点，比较两个链表头结点的值的大小。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode head1,
     ListNode head2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if(head1 != null){
            tmp.next = head1;
        }
        if(head2 != null){
            tmp.next = head2;
        }
        return newHead.next;
    }
}

CM11 链表分割

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
…            return as;
        }
        be.next = as;
        if(as !=null){
            ae.next = null;
        }
        return bs;
    }
}

OR36 链表的回文结构

题目Oj：OR36 链表的回文结构

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        if(head == null){
            return false;
        }
        if(head.next == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-01-03，如有侵权请联系 cloudcommunity@tencent.com 删除

null