前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍链表的位置改变与判断。

---

一、BM12 单链表的排序

（1）定义一个新的空链表，用来存储排序后链表；
（2）定义两个指针，一个用来标记当前最小，一个用来遍历寻找最小；
（3）找到最小值后，将最小值加入新链表，并删除最小节点；
（4）如此循环，直到遍历结束。

function sortInList( head ) {
    // write code here
    var newNode = new ListNode();
    var p = newNode;
    var addNode = new ListNode();
    addNode.next = head;
    while(addNode.next){
        var left = addNode;
        var right = left.next;
        while(right.next){
            if(left.next.val > right.next.val){
                left = right
            }
            right = right.next
        }
        p.next = new ListNode(left.next.val);
        left.next = left.next.next
        p = p.next
    }
    return newNode.next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、BM13 判断一个链表是否为回文结构

（1）首先定义新链表，保存原始的链表；
（2）反转原始链表，返回反转链表；
（3）依次比较两个链表的值，有值不同则返回false，都相同就返回true。

function isPail( head ) {
    // write code here
    var oldhead = new ListNode();
    var orehead = oldhead;
    var p = head;
    while(p){
        oldhead.next = new ListNode(p.val);
        p = p.next;
        oldhead = oldhead.next
    }

    var rehead= reverse(head)
    while(rehead){
        if(orehead.next.val != rehead.val){
            return false
        }
        rehead = rehead.next;
        orehead = orehead.next;
    }
    return true
}

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

三、BM14 链表的奇偶重排

（1）定义两个空链表，分别为左右链表；
（2）设置两个指针，一个遍历奇数节点，存入leftNode，一个遍历偶数节点，存入rightNode。
（3）拼接leftNode和rightNdoe，返回新链表。

function oddEvenList( head ) {
    // write code here
    if(head == null || head.next == null){
        return head
    }
    var rightNode = new ListNode();
    var leftNode = new ListNode();
    var p = leftNode;
    var q = rightNode;
    var left = head;
    var right = head.next;
    while(left || right){
        if(left != null){
            p.next = new ListNode(left.val);
            p = p.next;
            if(left.next){
                left = left.next.next
            }else{
                left = null
            }
        }
        if(right != null){
            q.next = new ListNode(right.val);
            q = q.next;
            if(right.next){
                right = right.next.next
            }else{
                right = null
            }
        }
    }
    p.next = rightNode.next;
    return leftNode.next;
}
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

四、BM15 删除有序链表中重复的元素-I

（1）定义快慢指针；
（2）如果快指针的值等于慢指针的值，则删除快指针，让慢指针的next指向快指针的next，快指针指向快指针的next；
（3）如果快指针的值不等于慢指针的值，则快慢指针都往后移。

function deleteDuplicates( head ) {
    // write code here
    if(head == null){
        return null
    }
    var slow = head;
    var fast = head.next;
    while(fast){
        if(slow.val != fast.val){
            slow = slow.next;
        }else{
            slow.next = fast.next;
        }
        fast = fast.next
    }
    return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

五、BM16 删除有序链表中重复的元素-II

（1）定义一个空链表，存储没有重复值的节点；
（2）定义两个指针slow fast，slow指向head，fast指向head.next；
（3）如果slow.val不等于fast.val，则将slow存入新链表，slow = slow.next，fast = fast.next；
（4）如果slow.val等于fast.val，则循环fast，直到slow.val不等于fast.val，slow = fast，fast = fast.next；
（5）如此循环，返回新链表。

function deleteDuplicates( head ) {
    // write code here
    if(head == null || head.next == null){
        return head
    }
    var newHead = new ListNode();
    var p = newHead;
    var left = head;
    var right = head;
    while(right != null){
        right = right.next;
        if(right == null || left.val != right.val){
            p.next = new ListNode(left.val)
            p = p.next
            left = left.next;
        }else{
            while(right != null && left.val == right.val){
                right = right.next
            }
            left = right;
        }
    }
    return newHead.next
    
}
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