劍指 Offer 18. 刪除鏈表的節(jié)點(diǎn)
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz4mp2/
時間復(fù)雜度:O(n)租谈,空間復(fù)雜度:O(1)
var deleteNode = function(head, val) {
if(head == null){
return null;
}
if(head.val == val){
return head.next;
}
var left = head;
var cur = left.next
while(cur.val != val && cur.next!= null){
left=cur;
cur=cur.next;
}
if(cur != null){
left.next=cur.next
}
return head
};
劍指 Offer 22. 鏈表中倒數(shù)第 k 個節(jié)點(diǎn)
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzy5ei/
時間復(fù)雜度:O(n)椅挣,空間復(fù)雜度:O(1)
var getKthFromEnd = function(head, k) {
var cur = head;
var post= head;
for(var i=0; i<k; i++){
cur = cur.next;
}
while(cur!=null){
cur = cur.next;
post = post.next
}
return post
};
劍指 Offer 24. 反轉(zhuǎn)鏈表
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzccxg/
時間復(fù)雜度:O(n)侥猬,空間復(fù)雜度:O(1)
var reverseList = function(head) {
var cur = null;
var pre = head;
while(pre!=null){
var tmp = pre.next;
pre.next = cur;
cur = pre;
pre = tmp;
}
return cur
};
劍指 Offer 25. 合并兩個排序的鏈表
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzjkjj/
輸入兩個遞增排序的鏈表榨了,合并這兩個鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的识颊。O(m+n)
var mergeTwoLists = function(l1, l2) {
if(l2==null){
return l1
}
if(l1==null){
return l2
}
if(l1.val>l2.val){
l2.next = mergeTwoLists(l1,l2.next);
return l2
}else{
l1.next = mergeTwoLists(l2,l1.next);
return l1
}
};
劍指 Offer 52. 兩個鏈表的第一個公共節(jié)點(diǎn)
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xshucr/
使用兩個指針 node1杂拨,node2 分別指向兩個鏈表 headA锡凝,headB 的頭結(jié)點(diǎn)杉女,然后同時分別逐結(jié)點(diǎn)遍歷贰剥,
當(dāng) node1 到達(dá)鏈表 headA 的末尾時头谜,重新定位到鏈表 headB 的頭結(jié)點(diǎn);
當(dāng) node2 到達(dá)鏈表 headB 的末尾時鸠澈,重新定位到鏈表 headA 的頭結(jié)點(diǎn)柱告。
這樣,當(dāng)它們相遇時笑陈,所指向的結(jié)點(diǎn)就是第一個公共結(jié)點(diǎn)际度。
- 時間復(fù)雜度:O(M+N)。
- 空間復(fù)雜度:O(1)O(1)涵妥。
//(雙指針法)
var getIntersectionNode = function(headA, headB) {
let curA = headA;
let curB = headB;
while (curA != curB) {
curA = curA != null ? curA.next : headB;
curB = curB != null ? curB.next : headA;
}
return curA;
};