【JavaScript】LeetCode：31-35

文章目录

31 反转链表
32 回文链表
33 环形链表
34 环形链表Ⅱ
35 合并两个有序链表

31 反转链表

在这里插入图片描述

初始化：cur = head，pre = null。
pre和cur一起向前移。
由于反转链表时，cur.next指向pre，导致cur在下次循环中就找不到了原来的cur.next，因此需要临时指针temp记录原来的cur.next。

javascript">/*** 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 || !head.next){return head;} var pre = null;var cur = head;while(cur){var temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
};

32 回文链表

在这里插入图片描述

方法1：将链表节点的val放入数组中，然后利用双指针判断是否为回文数组（i指向第一个元素，j指向最后一个元素）。
方法2：快慢指针，这里给出该方法的代码。
将后半部分反转，前半部分和后半部分链表比较。
快指针1次走2步，慢指针1次走1步。
快指针走到头，慢指针刚好到中间，此时这个中间点既是反转链表的起点。
后半部分链表反转后，利用双指针判断是否为回文链表（left指向前部分的头节点[整个链表的头节点]，right指向后半部分的头节点[整个链表最后一个节点]）。

javascript">/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/var reverseList = function(head) {if(!head || !head.next){return head;} var pre = null;var cur = head;while(cur){var temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
};var findMiddle = function(head) {var fast = head;var slow = head;while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}return slow;
}/*** @param {ListNode} head* @return {boolean}*/
var isPalindrome = function(head) {var mid = findMiddle(head);var right = reverseList(mid);var left = head;while(left != null && right != null){if(left.val != right.val){return false;}left = left.next;right = right.next;}return true;
};

33 环形链表

在这里插入图片描述

哈希集合
遍历链表节点，将节点放入Set中，若Set中已经存在该节点，则该链表存在环。

javascript">/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} head* @return {boolean}*/
var hasCycle = function(head) {var set = new Set();while(head != null){if(set.has(head)){return true;}set.add(head);head = head.next;}return false;
};

34 环形链表Ⅱ

在这里插入图片描述

方法1：哈希集合，遍历链表节点，将节点放入Set中，若Set中已经存在该节点，则该节点为入口的第一个节点。

javascript">/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} head* @return {ListNode}*/
var detectCycle = function(head) {var set = new Set();while(head != null){if(!set.has(head)){set.add(head);}else{return head;}head = head.next;}return null;
};

方法2：快慢指针。
快指针1次走2步，慢指针1次走1步。快指针绕圈了，快指针追慢指针。
假设：从链表头节点到入环的第一个节点的长度为x，入环的第一个节点到快、慢指针相遇点的长度为y，快、慢指针相遇点到入环的第一个节点的长度为z。
当快、慢指针相遇时，证明链表有环。
slow = x + y，fast = x + y + n(y + z)
2(x + y) = x + y + n(y + z)
x + y = n(y + z)
x = n(y + z) - y = (n - 1)(y + z) + z
n = 1时，x = z，即当头节点和相遇点一起向前走，二者指向的节点相等时，该节点为入环的第一个节点。

javascript">/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} head* @return {ListNode}*/
var detectCycle = function(head) {var fast = head;var slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){var i = head;var j = fast;while(i!= j){i = i.next;j = j.next;}return i;}}return null;
};

35 合并两个有序链表

在这里插入图片描述

哨兵节点：该节点无意义，从第2个节点开始才保存真正有意义的信息。具有哨兵节点的链表不需要单独处理输入头节点为null的情况。
比较两个链表的大小，val较小的节点，先链接到合并链表中。
当其中一个链表遍历完之后，结束循环，将另一个链表全部连接到合并链表中。

javascript">/*** 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) {var newNode = new ListNode(); var cur = newNode; while(list1 != null && list2 != null){if(list1.val < list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if(list1 != null){cur.next = list1;}if(list2 != null){cur.next = list2;}return newNode.next;
};