前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍两个链表的操作。

---

一、BM10 两个链表的第一个公共结点

（1）分别在两个链表的头部设置指针；
（2）当指针1到链表1尾部，就令指针1指向链表2，指针2也执行相同的操作；
（3）当指针1等于指针2时就是两个链表的交点，如果都为null，就是没有交点。

function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    var first = pHead1;
    var last = pHead2;
    if(pHead1 == null || pHead2 == null){
        return null
    }
    while(first != last){
        if(first == null){
            first = pHead2;
        }else{
            first = first.next
        }
        if(last == null){
            last = pHead1;
        }else{
            last = last.next
        }
    }
    return first
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、BM11 链表相加(二)

（1）首先将两个链表都反转，在两个链表的头部都用指针指向；
（2）如果两个指针都不为空，则将两个指针指向的数字相加，并按照加法的操作进位；
（3）如果有一个指针为空了，则证明数字到头了，那么就将不为空的指针与0相加，也按照加法的操作进位；
（4）两个链表的数字都加好以后，还要判断进位变量中是否有数字，如果有数字，则也放在新链表中；
（5）最后将得到的链表反转，就得到了相加以后的链表。

function addInList( head1 ,  head2 ) {
    // write code here
    var rhead1 = reverse(head1)
    var rhead2 = reverse(head2)
    var newNode = new ListNode();
    var p = newNode;
    var newNum = 0;
    var temp = 0;
    // 如果两个指针都不为空，则将两个指针指向的数字相加，并按照加法的操作进位
    while(rhead1 && rhead2){
        newNum = (rhead1.val+rhead2.val+temp)%10   //保存相加后的数字的个位
        temp = Math.floor((rhead1.val + rhead2.val+temp)/10)  //保存相加后的数字的十位
        p.next = new ListNode(newNum);  // 创建新节点，放在新链表的后面
        p = p.next
        rhead1 = rhead1.next
        rhead2 = rhead2.next
    }
    if(rhead2 == null){
        while(rhead1 != null){
            newNum = (rhead1.val+temp)%10
            temp = Math.floor((rhead1.val+temp)/10)
            p.next = new ListNode(newNum)
            p = p.next
            rhead1 = rhead1.next
        }
    }else{
        while(rhead2 != null){
            newNum = (rhead2.val+temp)%10
            temp = Math.floor((rhead2.val+temp)/10)
            p.next = new ListNode(newNum)
            p = p.next
            rhead2 = rhead2.next
        }
    }
    if(temp != 0){
        p.next = new ListNode(temp)
    }
    return reverse(newNode.next)
}

function reverse(head){
    var cur = head;
    var pre = null;
    while(cur){
        var temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51