JS 链表

链表题的一些总结

两种链表定义

• class

class ListNode {val;next = null;constructor(value) {this.val = value;this.next = null;}
}

• function

function ListNode(val, next) {this.val = val === undefined ? 0 : val;this.next = next === undefined ? null : next;
}

set存储链表节点，存的是整个空间

• 相交链表

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} headA* @param {ListNode} headB* @return {ListNode}*/
var getIntersectionNode = function(headA, headB) {const set = new Set();let tmp = headA;while(tmp) {if(!set.has(tmp)) {set.add(tmp);}tmp = tmp.next;}tmp = headB;while(tmp) {if(set.has(tmp)) {return tmp;}tmp = tmp.next;  }return null;
};

同时处理长短不一的两个链表

处理方法 while(l1 || l2)

• 两数相加

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var addTwoNumbers = function(l1, l2) {let head = new ListNode(0);let cur = head;let carry = 0;while(l1 != null || l2 != null) {const n1 = l1 != null ? l1.val : 0;const n2 = l2 != null ? l2.val : 0;let sum = n1 + n2 + carry;carry = Math.floor(sum / 10);sum = sum % 10;let tmp = new ListNode(sum, null);cur.next = tmp;cur = tmp;if(l1 != null) {l1 = l1.next;}if(l2 != null) {l2 = l2.next;}}if(carry === 1) {let tmp = new ListNode(1, null);cur.next = tmp;cur = tmp;}return head.next;
};

处理方法 while(l1 & l2)

不能用或，如果一个链表之后为空了，就没有比较的必要

• 合并有序链表
• 超出时间限制

var mergeTwoLists = function(list1, list2) {let dummyhead = new ListNode(-1);let h = dummyhead;while(list1 || list2) {if(list1 === null) {h.next = list2;} else if(list2 === null) {h.next = list1;} else {if(list1.val < list2.val) {h.next = list1;h = list1;list1 = list1.next;} else {h.next = list2;h = list2;list2 = list2.next;}}}return h.next;
};

• 不超出时间限制

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} list1* @param {ListNode} list2* @return {ListNode}*/
var mergeTwoLists = function(list1, list2) {let dummyhead = new ListNode(-1);let h = dummyhead;while(list1 && list2) {if(list1.val < list2.val) {h.next = list1;h = list1;list1 = list1.next;} else {h.next = list2;h = list2;list2 = list2.next;}}if(list1 === null) {h.next = list2;} else if(list2 === null) {h.next = list1;}return dummyhead.next;
};

dummyhead的使用

返回时 dummyhead.next