关于链表:算法链表

哨兵节点

哨兵节点是为了简化解决链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第 2 个节点开始才真正保留有意义的信息。

• 用哨兵节点简化链表插入操作
• 用哨兵节点简化链表删除操作

应用哨兵节点能够简化创立或删除链表头节点操作的代码。

双指针

21. 删除倒数第 k 个节点

题目：如果给定一个链表，请问如何删除链表中的倒数第 k 个节点？假如链表中节点的总数为 n，那么 1≤k≤n。要求只能遍历链表一次。

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {const dummy = new ListNode(0, head);
    let front = head, back = dummy;
    for(let i = 0;i<n;i++) {front = front.next}
    while(front !== null) {
        front = front.next;
        back = back.next
    }
    back.next = back.next.next
    return dummy.next

};

22. 链表中环的入口节点

题目：如果一个链表中蕴含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着 next 指针方向进入环的第 1 个节点为环的入口节点。例如，在如图 4.3 所示的链表中，环的入口节点是节点 3。

反转链表

24. 反转链表

题目：定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点

var reverseList = function(head) {
  const prev = null;
  const cur = head;
  while(cur != null) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next; 
  }
  return prev
}

25. 链表中的数组相加

题目：给定两个示意非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和依然用单向链表示意？链表中的每个节点示意整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。

剖析：要思考整数溢出的状况。

/**
 * 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) {
    let prev = null
    let cur = head
    while(cur !== null) {
        const next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
}


/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {let head1 = reverseList(l1)
    let head2 = reverseList(l2)
    let dummy = head = new ListNode(null)
    let sub = 0
    while(head1 !== null || head2 !== null) {
        let a = head1 !== null ?  head1.val :0
        let b = head2 !== null ? head2.val :0
        let val = a + b + sub
        let node
        if(val >= 10) {
            val = val - 10
            node = new ListNode(val)
            sub =  1
        } else {node = new ListNode(val)
            sub = 0
        }
        head.next = node
        head = head.next
        head1 && (head1 = head1.next)
        head2 && (head2 = head2.next)
    }
    if(sub==1) {head.next = new ListNode(1)
        head = head.next
    }
    return reverseList(dummy.next)
};

26. 重排链表

问题：给定一个链表，链表中节点的程序是 L0→L1→L2→…→Ln-1→Ln，请问如何重排链表使节点的程序变成 L0→Ln→L1→Ln-1→L2→Ln-2→…？

1. 切分链表
2. 反转后半链表
3. 链接链表

/**
 * 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) {
    let prev = null
    let cur = head
    while(cur!==null) {
        const next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
}

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {let dummy = new ListNode(0, head);
  let fast = dummy, slow = dummy;

  while(fast != null && fast.next != null) {
    slow = slow.next
    fast = fast.next.next
  }

  const temp = slow.next;
  slow.next = null;
  link(head, reverseList(temp), dummy);
}

var link = function(node1, node2, head) {
  let prev = head;
  while(node1 !== null && node2 !== null) {
    const temp = node1.next;
    prev.next = node1;
    node1.next = node2
    prev = node2

    node1 = temp
    node2 = node2.next
  }
  if(node1 !== null) {prev.next = node1}
}

27. 回文链表

问题：如何判断一个链表是不是回文？要求解法的工夫复杂度是 O（n），并且不得应用超过 O（1）的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是雷同的。例如，图 4.13 中的链表的节点序列从前往后看和从后往前看都是 1、2、3、3、2、1，因而这是一个回文链表。

/**
 * 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) {
    let prev = null
    let cur = head
    while(cur !== null) {
        const next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
}

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {if(head == null || head.next == null) {return true;}
  let slow = head;
  let fast = head.next;
  while(fast.next !== null && fast.next.next !== null) {
    slow = slow.next
    fast = fast.next.next
  }
  let secondHalf = slow.next;
  if(fast.next != null) {secondHalf = slow.next.next}
  slow.next = null;
  return equals(secondHalf, reverseList(head))
}

var equals = function(head1, head2) {while(head1 != null && head2 !== null){if(head1.val !== head2.val) return false

    head1 = head1.next
    head2 = head2.next
  }

  return head1 == null && head2 == null;
}

双向链表和循环链表

28. 展平多级双向链表

在一个多级双向链表中，节点除了有两个指针别离指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。请将这样的多级双向链表展平成一般的双向链表，即所有节点都没有子链表。

var flatten = function(head) {

}

var flattenGetTail = function() {}

29. 排序的循环链表

问题：在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保障插入节点之后的循环链表依然是排序的。