解题技巧
1、双指针解法
2、增加指向头节点的指针
3、递归
4、边界条件
题目一：删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
4 -> 5 -> 1 -> 9
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
思路
由于题目表明，链表至少包含两个节点，链表中所有节点的值都是唯一的， 给定的节点为非末尾节点并且一定是链表中的一个有效节点。因此，最直接的就是把指向待删除节点指针指向待删除节点的下一个节点。
但是无法获取前驱指针，因此考虑把待删除节点的下一个节点复制给待删除节点，然后删除下一个节点
AC代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
node.val=node.next.val
node.next=node.next.next
};
题目二：删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路
方法一：
用一个计数器记录链表的长度，然后找到倒数第n个节点删除。需要两次遍历
方法二：
使用两个指针，快指针要领先慢指针n+1，当快指针指向null时，慢指针的next节点就是要删除的倒数第n个节点。还要设置一个指向头节点的指针，头结点可能被删除。
AC代码
方法一
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
var cnt=0,node=head
while(node){
cnt++
node=node.next
}
if(cnt==1&&n==1){
head=null
return head
}
n=cnt-n
if(n==0){
head.val=head.next.val
head.next=head.next.next
return head
}
cnt=0
node=head
while(node){
cnt++
if(cnt==n){
node.next=node.next.next
return head
}
node=node.next
}
}
方法2
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
//注意代码的鲁棒性，首先对输入的参数做判断，为空啊，数字是0啊正，另一个判断n大于链表的情况
var removeNthFromEnd = function(head, n) {
if(!head||n==0)return null //空链表和倒数第0个返回null
var headPre=new ListNode(0)
headPre.next=head
var first=headPre,second=headPre
for(let i=1;i<=n+1;i++){
if(first.next){//防止n大于链表的长度
first=first.next//first要比second指针领先n+1，当firt指针指向null时，second指针的next就是要删除的节点 }else{
return null
}
}
while(first){
first=first.next
second=second.next
}
second.next=second.next.next
return headPre.next
};
题目三：反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路
方法一：将链表入栈，出栈的顺序就是反转链表
方法二：直接更改链表指针
AC代码
方法一
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
//递归
// if(head){
// if(!arr)
// var arr=[]
// arr.unshift(head.val)
// reverseList(head.next)
// }
//return arr
//迭代
var node=head,arr=[]
while(node){
arr.unshift(node.val)
node=node.next
}
return arr
};
方法二
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
var pre=null
while(head){
var t=head.next
head.next=pre
pre=head
head=t
}
return pre
};
题目四：合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路
归并排序的一部分。
AC代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*递归只判断一次，迭代是while
*/
var mergeTwoLists = function(l1, l2) {
if(!l1)return l2
if(!l2)return l1
var mergeHead=null
if(l1.val<=l2.val){
mergeHead=l1
mergeHead.next=mergeTwoLists(l1.next,l2)
}else{
mergeHead=l2
mergeHead.next=mergeTwoLists(l1,l2.next)
}
return mergeHead
};
题目五：回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路
链表对折相等。
方法一：
使用数组存储链表节点值，比较链表的前半部分节点值和数组元素的后半部分值。如果完全相等，则是，否则不是
方法二：
使用快慢指针，快指针是慢指针的两倍，当快指针指向null时，慢指针指向链表的后半部分节点，反转后半部分链表，然后和前半部分链表比较，如相等则是，否则不是
AC代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
//方法1
// var l=head,arr=[]
// while(l){
// arr.unshift(l.val)
// l=l.next
// }
// var len=arr.length
// for(let i=0;i<Math.floor(len/2);i++){
// if(head.val!=arr[i]){
// return false
// }else{
// head=head.next
// }
// }
// return true
//方法2，使用快慢指针
var fast=head,slow=head
while(fast&&fast.next){
fast=fast.next.next
slow=slow.next
}
slow = reverseList(slow)
while (slow != null) {
if (slow.val != head.val) return false
slow = slow.next
head = head.next
}
return true
};
var reverseList = function(head) {
let ans = null,
cur = head
while (cur != null) {
let nextTmp = cur.next
cur.next = ans
ans = cur
cur = nextTmp
}
return ans
};
题目六: 环形链表
给定一个链表，判断链表中是否有环。
进阶：
你能否不使用额外空间解决此题？
思路
如是环形链表，那么链表没有终值，不会指向null。假设在操场上跑步，跑的慢的同学会被跑的快的同学套圈，在发生套圈时，他们所在的位置相同。因此设置快慢指针，当慢指针和快指针同时指向一个节点，那么链表存在环，否则没有环。
判断边界条件，当链表为空时，直接返回false
AC代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
if(!head) return false
var slow=head,fast=head
while(slow&&fast&&fast.next){
slow=slow.next
fast=fast.next.next
if(slow==fast){
return true
}
}
return false
};
网友评论