刪除鏈表的倒數(shù)第N個節(jié)點(diǎn)
給你一個鏈表嗜憔，刪除鏈表的倒數(shù)第 n 個結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)氏仗。
示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]
// 快慢雙指針
var removeNthFromEnd = function(head, n) {
let star = new ListNode(0)//設(shè)置一個虛擬頭結(jié)點(diǎn)指向原頭結(jié)點(diǎn)吉捶，最后返回star.next即可
star.next = head
let left = star,right = star
// right先走n步
while(n){
n--
right = right.next
}
// right先走n步后right、left一起走皆尔，直到right走到最后一位（right.next=null）
while(right.next){
left = left.next
right = right.next
}
// right走到最后一位,此時left指向的是要刪除的節(jié)點(diǎn)的前一個節(jié)點(diǎn)
// 將此時結(jié)點(diǎn)指向下一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)呐舔，即刪除了此時節(jié)點(diǎn)的下一個節(jié)點(diǎn)（目標(biāo)結(jié)點(diǎn)）
left.next = left.next.next
return star.next
}
反轉(zhuǎn)鏈表
給你單鏈表的頭節(jié)點(diǎn) head ，請你反轉(zhuǎn)鏈表慷蠕，并返回反轉(zhuǎn)后的鏈表珊拼。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
var reverseList = function(head) {
let prev = null,curr = head
while(curr){
let next = curr.next
curr.next = prev
prev = curr
curr = next
}
console.log(head)
return prev
};
合并兩個有序鏈表
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的流炕。
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
var mergeTwoLists = function(l1, l2) {
let head = new ListNode(0)//設(shè)置一個頭結(jié)點(diǎn)澎现，并保存在這里，方便后續(xù)輸出結(jié)果鏈表
let prev = head//設(shè)置一個指針初始化指向頭結(jié)點(diǎn)每辟，比較大小向后移動
while(l1!=null&&l2!=null){//當(dāng)l1剑辫、l2都不為空時進(jìn)行比較
if(l1.val<l2.val){
prev.next = l1
l1=l1.next
}else{
prev.next = l2
l2 = l2.next
}
prev = prev.next
}
prev.next = l1==null?l2:l1//當(dāng)l1為空時，把剩余的l2追加到合并鏈表的后面
return head.next
};
回文鏈表
請判斷一個鏈表是否為回文鏈表渠欺。
示例 1:
輸入: 1->2->2->1
輸出: true
// 轉(zhuǎn)成數(shù)組妹蔽，通過快慢指針判斷
var isPalindrome = function(head) {
let arr = []
while(head){//先把鏈表遍歷到數(shù)組里
arr.push(head.val)
head = head.next
}
console.log(arr)
let left = 0,right = arr.length-1
while(left<right){
if(arr[left]!=arr[right]){
console.log('111')
return false
}else{
left++
right--
}
}
console.log(arr)
return true
};
// 這個是看了大佬的解題，很棒
var isPalindrome = function(head) {
let a = '',b = ''
while(head){
a=a+head.val
b=head.val+b
head = head.next
}
console.log(a,b)
return a==b
};
環(huán)形鏈表
給定一個鏈表，判斷鏈表中是否有環(huán)讹开。
如果鏈表中有某個節(jié)點(diǎn)盅视，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)旦万。 為了表示給定鏈表中的環(huán)闹击，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1成艘，則在該鏈表中沒有環(huán)赏半。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實(shí)際情況淆两。
如果鏈表中存在環(huán)断箫，則返回 true 。 否則秋冰，返回 false 仲义。
// 設(shè)置快慢指針，如果
var hasCycle = function(head) {
let p1=head,p2=head.next
while(p2){
p1 = p1.next
p2 = p2.next
if(p1==p2){
return true
}
}
return false
};
