链表
移除链表元素
思考
- 如果不使用虚拟头节点的话，需要每次check头节点，如果符合的话就将头节点设为头结点下一个节点
- 非头结点的链表，移除就是将前一个节点的next指向下一个节点
- 虚拟头节点可以理解成不检查头节点的方法
方法一 在原链表上直接删除
function removeElements(head: ListNode | null, val: number): ListNode | null {
// 删除头部节点
while (head !== null && head.val === val) {
head = head.next;
}
if (head === null) return head;
let pre: ListNode = head, cur: ListNode | null = head.next;
// 删除非头部节点
while (cur) {
if (cur.val === val) {
pre.next = cur.next;
} else {
//此处不加类型断言时：编译器会认为pre类型为ListNode, pre.next类型为ListNode | null
pre = pre.next as ListNode;
}
cur = cur.next;
}
return head;
};
方法二 虚拟头节点
function removeElements(head: ListNode | null, val: number): ListNode | null {
let dum = new ListNode(0,head),
cur = dum.next,pre = dum
while (cur) {
if (cur.val === val) {
pre.next = cur.next;
} else {
//此处不加类型断言时：编译器会认为pre类型为ListNode, pre.next类型为ListNode | null
pre = pre.next as ListNode;
}
cur = cur.next;
}
return dum.next;
};
设计链表
思考
- 有时候不给出 ListNode 所以要自己会写 ListNode
- 使用虚拟头节点
class MyLinkedList {
// 记录链表长度
private size: number;
private head: ListNode | null;
private tail: ListNode | null;
constructor() {
this.size = 0;
this.head = null;
this.tail = null;
}
// 获取链表中第 index个节点的值
get(index: number): number {
// 索引无效的情况
if (index < 0 || index >= this.size) {
return -1;
}
let curNode = this.getNode(index);
// 这里在前置条件下，理论上不会出现 null的情况
return curNode.val;
}
// 在链表的第一个元素之前添加一个值为 val的节点。插入后，新节点将成为链表的第一个节点。
addAtHead(val: number): void {
let node: ListNode = new ListNode(val, this.head);
this.head = node;
if (!this.tail) {
this.tail = node;
}
this.size++;
}
// 将值为 val 的节点追加到链表的最后一个元素。
addAtTail(val: number): void {
let node: ListNode = new ListNode(val, null);
if (this.tail) {
this.tail.next = node;
} else {
// 还没有尾节点，说明一个节点都还没有
this.head = node;
}
this.tail = node;
this.size++;
}
// 在链表中的第 index个节点之前添加值为 val的节点。
// 如果 index等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果 index小于0，则在头部插入节点。
addAtIndex(index: number, val: number): void {
if (index === this.size) {
this.addAtTail(val);
return;
}
if (index > this.size) {
return;
}
// <= 0 的情况都是在头部插入
if (index <= 0) {
this.addAtHead(val);
return;
}
// 正常情况
// 获取插入位置的前一个 node
let curNode = this.getNode(index - 1);
let node: ListNode = new ListNode(val, curNode.next);
curNode.next = node;
this.size++;
}
// 如果索引 index有效，则删除链表中的第 index个节点。
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) {
return;
}
// 处理头节点
if (index === 0) {
this.head = this.head!.next;
// 如果链表中只有一个元素，删除头节点后，需要处理尾节点
if (index === this.size - 1) {
this.tail = null
}
this.size--;
return;
}
// 索引有效
let curNode: ListNode = this.getNode(index - 1);
curNode.next = curNode.next!.next;
// 处理尾节点
if (index === this.size - 1) {
this.tail = curNode;
}
this.size--;
}
// 获取指定 Node节点
private getNode(index: number): ListNode {
// 这里不存在没办法获取到节点的情况，都已经在前置方法做过判断
// 创建虚拟头节点
let curNode: ListNode = new ListNode(0, this.head);
for (let i = 0; i <= index; i++) {
// 理论上不会出现 null
curNode = curNode.next!;
}
return curNode;
}
}
反转链表
思考
- 双指针法(要理解，为什么得先将pre赋值为cur，而不是cur先赋值为tmp)
- 递归
方法一 双指针法
function reverseList(head: ListNode | null): ListNode | null {
let pre = null
let cur = head
let tmp = null
while(cur!==null){
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
}
return pre
};
方法二 递归法
function reverseList(head: ListNode | null): ListNode | null {
if(head===null||head.next===null){
return head
}
let cur = reverseList(head.next)
head.next.next = head
head.next = null
return cur
};
两两交换链表中的节点
思考
- 这个题目最好画图理解，一步一步走下来流程就很清楚了
- 需要两个tmp，边界问题要避免空指针
- 虚拟头节点
function swapPairs(head: ListNode | null): ListNode | null {
let dum = new ListNode(0,head),cur = dum,tmp1,tmp2
while(cur.next!==null&&cur.next.next!==null){
tmp1 = cur.next
tmp2 = cur.next.next.next
cur.next = tmp1.next
cur.next.next = tmp1
tmp1.next = tmp2
cur = cur.next.next
}
return dum.next
};
删除链表的倒数第N个结点
思考
- 要删除一个节点要将操作结点cur指向这个节点的上一个节点
- 因为是倒数第N个节点，所以我们可以设计一对快慢指针，让快指针先跑N步，然后再一起跑，等到快指针的next跑到null的时候，慢指针的next就指向倒数第N个节点
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let dum = new ListNode(0,head),cur = dum,fast = dum
while(n--){
fast = fast.next
}
while(fast.next){
cur = cur.next
fast = fast.next
}
cur.next = cur.next.next
return dum.next
};
链表相交
思考
- 要理解，如果链表相交，后面全部都是相同的，因此可以直接让这两条链从末尾开始对其然后开始比较
var getListLen = function(head) {
let len = 0, cur = head;
while(cur) {
len++;
cur = cur.next;
}
return len;
}
var getIntersectionNode = function(headA, headB) {
let curA = headA,curB = headB,
lenA = getListLen(headA), // 求链表A的长度
lenB = getListLen(headB);
if(lenA < lenB) { // 让curA为最长链表的头，lenA为其长度
// 交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
// 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
[curA, curB] = [curB, curA];
[lenA, lenB] = [lenB, lenA];
}
let i = lenA - lenB; // 求长度差
while(i-- > 0) { // 让curA和curB在同一起点上（末尾位置对齐）
curA = curA.next;
}
while(curA && curA !== curB) { // 遍历curA 和 curB，遇到相同则直接返回
curA = curA.next;
curB = curB.next;
}
return curA;
};
环形链表
思考
首先要证明这是个环形链表，要做的是定义一个快指针一个慢指针，他们速度差值为1，这样就不会跳过了。当慢指针等于快指针的时候就证明了这是个环形链表
要找出环形链表的入口，就得理解一个思路
- 最后写出代码
function detectCycle(head: ListNode | null): ListNode | null {
let fast = head,slow = head,index1,index2;
while(fast!==null&&fast.next!==null)
{
fast = fast.next.next
slow = slow.next
if(fast===slow){
index1 = fast
index2 = head
while(index1!==index2){
index1 = index1.next
index2 = index2.next
}
return index1
}
}
return null
};