算法 - 链表 - 简单

1、删除链表中的节点(太简单)

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 — head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

解答：

/**
 * 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
};

2、反转链表（太简单）

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let [pre, node] = [null, head];
    while(node){
        const temp = node.next;
        node.next = pre;
        pre = node;
        node = temp;
    }
    return pre;
};

3、剑指 Offer 06. 从尾到头打印链表（利用递归形成的栈反转，最后一个元素和越界元素的处理，是精髓）

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：**

输入：head = [1,3,2]
输出：[2,3,1]

解答：

// 利用递归形成的栈反转链表
var reversePrint = function(head) {
        if(!head) return [];
        let value = head.val;
        let arr = reversePrint(head.next);
        arr.push(value)
        return arr;
};

4、回文链表（很麻烦，要找中间节点，然后反转，最后比较）

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

解答：**

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(!head) return true;
    let l2 = secoundLinkHead = l3 = head;
    let pre = null;
    while(l2.next && l2.next.next){
        secoundLinkHead = secoundLinkHead.next;
        l2 = l2.next.next;
    }
    const temple = secoundLinkHead.next;
    secoundLinkHead.next = null;
    secoundLinkHead = temple;
    while(secoundLinkHead){
        let temple = secoundLinkHead.next;
        secoundLinkHead.next = pre;
        pre = secoundLinkHead;
        secoundLinkHead = temple;
    }
    while(pre){
        if(pre.val !== l3.val){
            return false;
        }
        pre = pre.next;
        l3 = l3.next;
    }
    return true;
};

5、移除链表元素 (使用哨兵节点)

删除链表中等于给定值 val 的所有节点。
示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  const dummpy = pre =new ListNode()
  dummpy.next = head
  while(head){
    if(head.val === val){
        pre.next=head.next;
     }else{
       pre=head
     }
     head=head.next
  }
  return dummpy.next;
};

6、环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例1:

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
};

7、删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解答：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let pre = new ListNode(-1);
    let dummy = head;
    pre.next = head;
    while(dummy){
        if(pre.val  === dummy.val){
            pre.next = dummy.next;
            dummy = dummy.next;
        } else {
            let temp = dummy.next;
            pre = dummy;
            dummy = temp;
        }
    }
    return head;
};