[代码随想录打卡 Day3] 链表理论基础 203.移除链表元素 707.设计链表 206.反转链表

时间：2024-11-03 07:04:42

(ง •_•)ง今天出去玩了，只刷完了视频，做了部分题，就是具体整理明天整理。希望坚持下去。啊啊啊啊啊啊啊啊啊啊啊

链表理论基础

在这里插入图片描述
基础的就是单链表。
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链表的入口节点称为链表的头结点也就是head。
一般程序让你得到一个链表，就是返回他的头指针。
看代码比较直观。

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

203.移除链表元素

分两步，找到+删除。用cur.next的值判断是否是需要删除的节点，如果不是就cur = cur.next遍历到下一个节点。如果是，就cur = cur.next.next删除，C++需要手动释放内存。
这里面有个问题是如果头指针是需要删除的节点怎么办，正常就是判断分两种情况。太麻烦。我们就引入虚拟头节点，让虚拟头节点的next指针指向head头节点，这样头节点和中间节点的处理方式就统一了。返回的时候，只要返回虚拟头节点的next即可。

/**
 * 方法1
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val) {
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null && curr.next !=null) {
        if(curr.next.val == val){
            curr.next = curr.next.next;
        } else {
            curr = curr.next;
        }
    }
    return head;
}

/**
 * 方法1
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}


（版本一）虚拟头节点法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 创建虚拟头部节点以简化删除过程
        dummy_head = ListNode(next = head)
        
        # 遍历列表并删除值为val的节点
        current = dummy_head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy_head.next

707.设计链表

206.反转链表（看视频讲解，顶呱呱）

参考的题目、文章、视频

  1. https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%93%BE%E8%A1%A8%E7%9A%84%E7%B1%BB%E5%9E%8B
  2. https://leetcode.cn/problems/remove-linked-list-elements/description/
  3. https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
  4. https://www.bilibili.com/video/BV18B4y1s7R9/?vd_source=145b0308ef7fee4449f12e1adb7b9de2
  5. https://leetcode.cn/problems/design-linked-list/description/
  6. https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
  7. https://www.bilibili.com/video/BV1FU4y1X7WD/?vd_source=145b0308ef7fee4449f12e1adb7b9de2
  8. https://leetcode.cn/problems/reverse-linked-list/description/
  9. https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
  10. https://www.bilibili.com/video/BV1nB4y1i7eL/?vd_source=145b0308ef7fee4449f12e1adb7b9de2

相关文章