31 反转链表

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

/**
 * 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指向后半部分的头节点[整个链表最后一个节点]）。

/**
 * 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中已经存在该节点，则该链表存在环。

/**
 * 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中已经存在该节点，则该节点为入口的第一个节点。

/**
 * 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，即当头节点和相遇点一起向前走，二者指向的节点相等时，该节点为入环的第一个节点。

/**
 * 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较小的节点，先链接到合并链表中。
• 当其中一个链表遍历完之后，结束循环，将另一个链表全部连接到合并链表中。

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