题目链接:https://leetcode.cn/problems/remove-linked-list-elements/
链表的定义具有递归的性质,因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点,可以用递归实现。
对于给定的链表,首先对除了头节点 head 以外的节点进行删除操作,然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val,则 head 需要被删除,因此删除操作后的头节点为 head.next;如果 head 的节点值不等于 val,则 head 保留,因此删除操作后的头节点还是 head。上述过程是一个递归的过程。
递归的终止条件是 head 为空,此时直接返回 head。当 head 不为空时,递归地进行删除操作,然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
if (head === null) {
return head;
}
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
// 删除头结点
while (head != null && head.val == val) {
// 注意这里不是if
head = head.next; // 将头结点向后移动一位
}
// 删除非头结点
let cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
const dummyHead = new ListNode(0, head); // 设置一个虚拟头结点, 并且将虚拟头结点指向head,这样方面后面做删除操作
// 等价于 const dummyHead = new ListNode(0); dummyHead.next = head;
let cur = dummyHead;
while (cur.next) {
if (cur.next.val === val) {
cur.next = cur.next.next;
continue;
}
cur = cur.next;
}
return dummyHead.next; // dummyHead.next 是新的头结点
};
题目链接:https://leetcode.cn/problems/reverse-linked-list/
借助栈的后入先出的顺序,可以将顺序列表逆序。不过这不是原地反转,当然题目也没有要求。
处理过程如下:
1)从头到尾遍历链表,将节点val
依次放入栈
2)从栈中依次取出val
,构造新节点,并连接节点
时间复杂度O(N)
,空间复杂度O(N)
。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head) {
return null;
}
const stack = [];
let node = head;
while (node) {
stack.push(node.val);
node = node.next;
}
// 构造新节点
const newHead = {
val: stack.pop(),
next: null,
};
// 连接节点
node = newHead;
while (stack.length) {
node.next = {
val: stack.pop(),
next: null,
};
node = node.next;
}
return newHead;
};
“原地反转”的思路简单,但是实现起来有一些细节需要处理。链表类的原地操作,大部分都是细节上容易出错,导致死循环或者报错。
准备当前节点node
,和node
的前一个节点preNode
。整体的思路如下:
1)保留当前节点的下一个节点
2)将当前节点的next
指向前一节点preNode
3)更新preNode
为当前节点,更新当前节点为第一步保留的下一节点
4)判断当前节点是否是最后节点,如果不是,回到第一步;如果是,进入最后一步
5)将当前节点的next
指向前一节点preNode
时间复杂度是O(N)
,空间复杂度是O(1)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (!head) {
return null;
}
let node = head;
let preNode = null;
while (node.next) {
const nextNode = node.next;
node.next = preNode;
preNode = node;
node = nextNode;
}
node.next = preNode;
return node;
};
首先定义一个 cur 指针, 指向头结点, 再定义一个 pre 指针, 初始化为 null。
然后就要开始反转了, 首先要把 cur->next 节点用 tmp 指针保存一下, 也就是保存一下这个节点。
为什么要保存一下这个节点呢, 因为接下来要改变 cur->next 的指向了, 将 cur->next 指向 pre, 此时已经反转了第一个节点了。
接下来, 就是循环走如下代码逻辑了, 继续移动 pre 和 cur 指针。
最后, cur 指针已经指向了 null, 循环结束, 链表也反转完毕了。F 此时我们 return pre 指针就可以了, pre 指针就指向了新的头结点。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let curr = head;
let prev = null;
while (curr) {
const temp = curr.next; // 保存一下 cur的下一个节点, 因为接下来要改变cur->next
curr.next = prev; // 翻转操作
// 更新pre 和 cur指针
prev = curr;
curr = temp;
}
return prev;
};
题目链接:https://leetcode.cn/problems/design-linked-list/