欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

LeetCode初级之链表

程序员文章站 2024-03-06 21:08:26
...

链表

在本节的练习题中，有一点需要注意：题目中的链表都是不带头指针的链表，即head指向的是第一个节点

如果忽略了这一点，那么本地测试结果就与在线结果不一致

1.删除链表中的节点

问题
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

4 -> 5 -> 1 -> 9

示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

langage C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
}

思路

删除链表中的节点的正常的逻辑是这样的：

  • 两个指针：p、q，q指向p的前趋
  • 从头节点开始遍历，当p匹配到待删除节点时

伪代码

//p:待删除
q->next=p->next;
delete p;

但是本题有两个很重要的点：

  • 只给了一个待删除的节点，没有给头指针
  • 待删除节点非末尾节点

所以可以这样做：

  • 将待删除节点的后继节点复制到待删除节点上
  • 将后继节点删除

伪代码

//p:待删除节点，且非末尾节点
Node* tmp=p->next;
p->val=tmp->val;
p->next=tmp->next;
delete tmp;

解法

c语言解法

void deleteNode(struct ListNode* node) {
    if(node->next==NULL) return; 
    node->val=node->next->val;
    struct ListNode* tmp=node->next;
    node->next=tmp->next;
}

2.删除链表的倒数第N个节点

问题

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

  • 给定的 n 保证是有效的。

进阶：

  • 你能尝试使用一趟扫描实现吗？

langage C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {

}

思路

最普通的方法：

  • 扫一遍链表求出链表长度len
  • 计算待删除节点的位置m=len-n+1
  • 再扫一遍链表将第m个节点删除
    • 两个指针p、q，p在前，q保存p的前趋节点
    • q->next=p->next;

一遍扫描：

  • 三个指针

    • p ：快指针，比慢指针多走n个节点
    • q ：慢指针，该指针最终指向的节点即是待删除节点
    • m ：指向慢指针的前趋节点

  • 删除方法

考虑了头指针，这里的头指针是第一个节点，如果删除的是第一个节点，那么就不可以用m指针来删除

    if(q==head){
        head=head->next;
    }else{
        m->next=m->next->next;
    }

解法
c语言解法

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {/
    //p ：快指针，比慢指针多走n个节点
    //q ：慢指针，该指针最终指向的节点即是待删除节点
    //m ：指向慢指针的前趋节点
    struct ListNode *p,*q,*m;
    p=head;
    q=head;
    m=NULL;

    if(head==NULL||n<=0) return NULL;

    //p先走n-1个
    for(int i=1;i<n;i++){
        if(p->next){
            p=p->next;
        }else{
            return NULL;
        }
    }

    //此时，p指向第n个，q指向第1个，m指向NULL
    //p继续，q、m跟上
    while(p->next){
        p=p->next;
        m=q;
        q=q->next;
    }

    //m是待删除节点
    //删除时要考虑到是否删除的是第一个节点
    if(q==head){
        head=head->next;
    }else{
        m->next=m->next->next;
    }

    return head;
}

3.反转链表

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

  • 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

langage Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

    }
}

思路

三个指针：

  • p：指向待处理节点
  • q：指向待处理节点的前一个节点，默认为NULL
  • pr：指向待处理节点的后继节点

根据例子理解一下算法的过程：

初始链表状态
LeetCode初级之链表

初始化

  • p指针指向节点1
  • pr指针指向节点1
  • q指针指向NULL

反转节点1

  • 此时p指针指向节点1；pr指针指向节点1；q指针指向NULL
  • pr指向p的后继节点，作用只是保存，反转之后p的后继节点要从节点2变为NULL
  • 将p的后继节点改为q
  • 修改q指针指向为p
  • 修改p指针指向pr

反转节点2

  • 此时p指针指向节点2；pr指针指向节点2；q指针指向节点1
  • pr指向p的后继节点，作用只是保存，反转之后p的后继节点要从节点3变为节点1
  • 将p的后继节点改为q
  • 修改q指针指向为p
  • 修改p指针指向pr

反转节点3

  • 此时p指针指向节点3；pr指针指向节点3；q指针指向节点2
  • pr指向p的后继节点，作用只是保存，反转之后p的后继节点要从节点4变为节点2
  • 将p的后继节点改为q
  • 修改q指针指向为p
  • 修改p指针指向pr

反转节点4

  • 此时p指针指向节点4；pr指针指向节点4；q指针指向节点3
  • pr指向p的后继节点，作用只是保存，反转之后p的后继节点要从NULL变为节点3
  • 将p的后继节点改为q
  • 修改q指针指向为p
  • 修改p指针指向pr

修正头指针

继续向下移动的话，pr会指向NULL，此时跳出循环

整个链表除了头指针都被反转了，所以此时只要将头指针由节点1改为节点4即可

解法

java解法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode p=head,q=null,pr=head;

        while(pr!=null){
            pr=p.next;
            p.next=q;
            q=p;
            p=pr;
        }
        head=q;
        return head;
    }
}

4.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

langage Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    }
}

思路

三个指针：

  • pa：指向链表a
  • pb：指向链表b
  • lc：新链表的头指针
  • pc：指向lc，遍历时不影响头指针

从pa，pb指向的节点中选一个值小的节点，选中之后将该节点连接到新链表中，并继续向后移动

如果pa、pb有一个指向了NULL，那么只需要将另一个链表的剩余部分连接到新链表末尾即可

解法
java解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pa=l1,pb=l2;
        ListNode l3=new ListNode(-1);
        ListNode pc=l3;

        //从pa、pb中选取值小的节点连到新链表中
        while(pa!=null&&pb!=null){
            if(pa.val<pb.val) {
                pc.next=pa;
                pc=pa;
                pa=pa.next;
            }else{
                pc.next=pb;
                pc=pb;
                pb=pb.next;
            }
        }

        //将没有遍历结束的链表直接放到新链表末尾
        if(pa!=null) pc.next=pa;
        else pc.next=pb;

        l3=l3.next;
        return l3;
    }
}

5. 回文链表

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true

进阶：

  • 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

langage Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {

    }
}

思路

  • 扫一遍计算出链表长度n
  • 再扫一遍，边扫边反转，扫描到链表的1/2位置
  • 指针分离，从中间向左向右移动并比较，如果不同就返回false,比较到末尾未发现不同，则返回true

解法

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        int n=0;
        ListNode root=head;

        //计算链表长度
        while(root!=null){
            root=root.next;
            n++;
        }

        int i=0;
        ListNode m=null,p=head,q=head;
        //反转左半部分的链表
        while(i<n/2){
            q=p.next;
            p.next=m;
            m=p;
            p=q;
            i++;
        }

        //考虑奇偶
        if(n%2!=0) q=q.next;

        //指针分离，比较
        while(q!=null){
            if(q.val!=m.val) return false;
            q=q.next;
            m=m.next;
        }
        return true;
    }
}

6.环形链表

给定一个链表，判断链表中是否有环。

进阶：

  • 你能否不使用额外空间解决此题？

langage Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {

    }
}

思路

思路1（不太正确）：每经过一个节点时先判断是否有标记，如果没有标记说明它是一个新的节点，继续访问即可，如果有标记说明以前访问过，出现了环，返回true即可，链表遍历结束，没有发现环，返回false

思路2：快、慢指针，快指针每次走两个，慢指针每次有1个，当快、慢指针相遇时说明出现了环

解法

java解法(错误解法，已废弃)
该解法是我第一次想到的方法，是不正确的，我的最开始思路是遇到一个节点就标记，当遍历到节点先看看有没有被标记，我用了Integer.MAX_VALUE来标记，如果测试集中有这个值，那么结果就不正确了

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode root=head;
        if(head==null) return false;
        while(root!=null){
            if(root.val==Integer.MAX_VALUE) return true;
            root.val=Integer.MAX_VALUE;
            root=root.next;
        }
        return false;
    }
}

正确的解法

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;
        ListNode fast,low;
        fast=head;
        low=head;

        while(low!=null&&fast!=null&&fast.next!=null){
            fast=fast.next.next;
            low=low.next;
            if(fast==low) return true;
        }
        return false;
    }
}
相关标签： leetcode java 链表

上一篇： 单链表的学习

下一篇： Java实现快速排序过程分析

推荐阅读