代码随想录——链表 刷题记录

2023-12-16 17:40:37

链表数据结构

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;
	}
}

203.移除链表元素

707.设计链表

  • 单链表
  • 双链表
public static class DoubleListNode {
        int val;
        DoubleListNode prev;
        DoubleListNode next;

        public DoubleListNode() {
        }

        public DoubleListNode(int val) {
            this.val = val;
        }

        public DoubleListNode(int val, DoubleListNode prev, DoubleListNode next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
  • 注意参数index的大小范围判断

206.反转链表

  • 原地反转,更改每个节点的node值
  1. 迭代法(设置一个temp用来暂时保存下一位节点)
while (p != null) {
    temp = p.next;
    p.next = pre;
    pre = p;
	p = temp;
}
  1. 递归法(和迭代法思想相似,每次递归prev和cur)
  2. 虚拟头节点头插法
  3. 栈(节点入栈,注意最后一个弹出的节点next为空)
// 创建栈
Stack<ListNode> stackNode = new Stack<ListNode>();

24.两两交换链表中的节点

  • 先定义一个prev的值就好,pq的值可以在while中定义

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

  • 快慢指针法,快指针先移动n,然后一起移动,让slow停在删除的前一个位置

面试题02.07 链表相交

  • 算出AB链表的长度值,将长的链表指针先移动长度差值,然后一起移动判断节点是否相等

142.环形链表II

视频讲解
可以把环分成x, y, z,分析三者之间的数学关系

  • 慢指针不到一圈就被快指针追上
  • 快慢指针相遇的位置到环入口距离 = 链表头到环入口的距离

文章来源:https://blog.csdn.net/qq_43541423/article/details/135000767
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。