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

链表数据结构

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

2. 递归法（和迭代法思想相似，每次递归prev和cur）
3. 虚拟头节点头插法
4. 栈（节点入栈，注意最后一个弹出的节点next为空）

// 创建栈
Stack<ListNode> stackNode = new Stack<ListNode>();

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

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

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

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

面试题02.07 链表相交

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

142.环形链表II

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

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