中级算法 链表

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

---

---

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

TIP

思路就是逐位相加和进位

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

function add(val1, val2, carry) {
    let val = val1 + val2 + carry;
    if(val >=10) {
        return [val - 10, 1]
    }
    return [val, 0]
}

var addTwoNumbers = function(l1, l2) {
    let point1 = l1;
    let point2 = l2;
    let [val, carry] = add(point1.val , point2.val, 0)
    const node = {
        val: val,
        next: null
    }
    let curr = node;
    point1 = point1.next
    point2 = point2.next
    while(point1 || point2 || carry) {
        let [val, _carry] = add( point1 && point1.val || 0, point2 && point2.val || 0, carry)
        carry = _carry
        curr.next = {
            val: val,
            next: null
        }
        curr = curr.next;
        point1 && (point1 = point1.next)
        point2 && (point2 = point2.next)
    }
    return node
    
};

奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

---

---

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

/**
 * 代码写的很难看，凑合看，后续优化
 */
/**
 * 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 oddEvenList = function(head) {
    if(!head) {
        return head;
    }
    let index = 3;
    let odd = head; // 1
    if(!head.next) {
        return head;
    }
    let even = head.next; // 2
    const evenH = even;
    let curr = head.next
    while(curr.next) {
        curr = curr.next; // 3
        if(index % 2 === 0) {
            even.next = curr;
            even = even.next;
        } else {
            odd.next = curr;
            odd = odd.next;
        }
        index++;
        
    }
    even.next = null;
    odd.next = evenH;    
    return head;
};

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

---

---

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

/**
 * 这个交换有点厉害，没写出来
 */
/**
 * 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) {
    if (headA == null || headB == null) return null;
    let pA = headA, pB = headB;
    while(pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
};