1
2
3
思想：
1）由于头节点没有前一个节点，操作存在困难，所以可以考虑哑节点
2）画图

JS中自定义链表

1
2
3
4
5
6
7
8
class ListNode{
    val;
    next = null;
    constructor(value){
        this.val = value;
        this.next = null;
    }
}

问题：移除链表元素

问题描述：删除链表中等于给定值 val 的所有节点

示例：

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

注意点：

1
2
1. 直接使用原来的链表来进行删除操作
2. 为了操作便利，考虑到头节点的特殊，需要设置一个虚拟头节点来进行删除操作

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElements = function(head, val){
    const ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
            //不能直接cur=cur.next，会漏掉某些节点
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
}

问题：设计链表

问题描述：

1
2
3
4
5
6
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

解法

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class ListNode{
	constructor(val, next){
        this.val = val;
        this.next = next;
    }
}
//单链表存储头尾节点和节点数量
var MyLinkedList = function(){
    this._size = 0;
    this._tail = null;
    this._head = null;
}
MyLinkedList.prototype.getNode = function(index){
    if(index<0||index>=this._size)
        return null;
    let cur = new LinkNode(0, this._head);
    while(index-- >= 0)
        cur = cur.next;
    return cur;
}
MyLinkedList.prototype.get = function(index){
    if(index<0||index>=this._size)
        return null;
    return this.getNode(index).val;
}
MyLinkedList.prototype.addAtHead = function(val){
    const node = new LinkNode(val, this._head);
    this._head = node;
    this._size++;
    if(!this._tail)
        //当这个链表是空链表的情况
        this._tail = node;
}
MyLinkedList.prototype.addAtTail = function(val){
    const node = new LinkNode(val, null);
    this._size++;
    if(this._tail){
        this._tail.next = node;
        this._tail = node;
        return;
    }
    this._tail = node;
    this._head = node;
}
MyLinkedList.prototype.addAtIndex = function(index, val){
    if(index>this._size)
        return;
    if(index<=0){
        this.addAtHead(val);
        return;
    }
    if(index===this._size){
        this.addAtTail(val);
        return;
    }
    const node = this.getNode(index-1);
    //这里容易搞混：node.next是new LinkNode，而new LinkNode是node.next
    node.next = new LinkNode(val, node.next);
    this._size++;
}
MyLinkedList.prototype.deleteAtIndex = function(index){
    if(index<0||index>=this._size)
        return;
    if(index===0){
        this._head = this._head.next;
        if(index===this._size-1)
            //要删除的节点既是头节点，又是尾节点，则处理尾节点
            this._tail = this._head;
        this._size--;
        return;
    }
    const node = this.getNode(index-1);
    node.next = node.next.next;
    if(index===this._size-1)
        this._tail = node;
    this._size--;
}

//使用方法
var obj = new MyLinkedList()
var param_1 = obj.get(index)
obj.addAtHead(val)
obj.addAtTail(val)
obj.addAtIndex(index,val)
obj.deleteAtIndex(index)

问题：反转链表

问题描述：

1
2
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

反转示意图

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
var reverseList = function(head){
    if(!head || !head.next)
        return head;
    //temp用于存储下一个需要遍历的节点
    let temp = null, pre = null, cur = head;
    while(cur){
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

问题：两两交换链表中的节点

问题描述：

1
2
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

交换示例

解法图示：

两两反转图示

解法：

1
2
3
4
5
6
7
8
9
10
11
var swapPairs = function(head){
    let ret = new ListNode(0, head), temp = ret;
    while(temp.next && temp.next.next){
        let cur = temp.next.next, pre = temp.next;
        pre.next = cur.next;
        cur.next = pre;
        temp.next = cur;
        temp = pre;
    }
    return ret.next;
}

问题：链表中的节点每k个一组翻转

链接：

链表中的节点每k个一组翻转

描述：

1
2
3
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

示例：

1
2
输入：{1,2,3,4,5},2
返回值：{2,1,4,3,5}

思路：

思路

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function reverseKGroup( head ,  k ) {
    // 首先先分组，然后组内翻转，最后将翻转后的分组连接
    // 递归
    let tail = head;
    for(let i=0;i<k;i++){
      // 不足k到了链表尾直接返回不翻转
      if(!tail)
        return head;
      tail = tail.next;
    }
    let pre = null;
    let cur = head;
    while(cur!==tail){
      let temp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = temp;
    }
    head.next = reverseKGroup(tail, k);
    return pre;
}

问题：链表中倒数第k个节点

问题描述：

1
2
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1
2
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
var getKthFromEnd = function(head, k) {
    let slow = head, fast = head;
    while(k--&&fast)
        fast = fast.next;
    if(!fast)
        return head;
    while(fast.next){
        fast = fast.next;
        slow = slow.next;
    }
    // 为与下一题统一，统一找到第k个节点的前一个节点
    return slow.next;
};

问题：删除链表的倒数第N个节点(与上一题的区别是需要找到删除节点的前一个节点)

问题描述：

1
2
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

示例：

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

思路：

1
双指针，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，删掉slow所指向的节点就可以了

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var removeNthFromEnd = function(head, n){
    let slow=head, fast=head;
    while(n--&&fast!=null)
        fast = fast.next;
    //说明删除的是头节点，因为是倒数第N个节点
    if(fast===null)
        return head.next;
    while(fast.next!==null){
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

问题：链表相交

问题描述：

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

示例：

链表相交图示

解法图示：

链表解法图示

解法步骤：

1
2
3
1. 让curA指向链表A的头结点，curB指向链表B的头结点
2. 求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
3. 比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var getListLen = function(head){
	let len = 0, cur = head;
    while(cur){
        len++;
        cur = cur.next;
    }
    return len;
}
var getIntersectionNode = function(headA, headB){
    let curA = headA, curB = headB;
    let lenA = getListLen(curA), lenB = getListLen(curB);
    if(lenA < lenB){
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }
    let i = lenA - lenB;
    while(i-- > 0)
        curA = curA.next;
    while(curA&&curA!==curB){
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
}

问题：环形链表

问题描述：

1
2
3
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例：

环形链表

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var hasCycle = function(head) {
    if(!head)
        return false;
    let slow = head;
    let fast = head;
    while(fast){
        slow = slow.next;
        if(fast.next)
            fast = fast.next.next;
        else 
            return false;
        if(slow===fast)
            return true;
    }
    return false;
};

问题：环形链表II(与i的区别在于是否需要返回相交节点)

问题描述：

1
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例：

环形链表图示

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var detectCycle = function(head) {
    if(!head)
        return null;
    let slow = head, fast = head;
    while(fast.next && fast.next.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow===fast){
            let cur = head;
            while(cur!==slow){
                cur = cur.next;
                slow = slow.next;
            }
            return cur;
        }
    }
    return null;
};

两数相加

描述：

1
2
3
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var addTwoNumbers = function(l1, l2){
    let head = null, tail = null;
    let carry = 0;
    while(l1 || l2){
        const n1 = l1?l1.val:0;
        const n2 = l2?l2.val:0;
        const sum = n1+n2+carry;
        if(!head)
            head = tail = new ListNode(sum%10);
        else{
            tail.next = new ListNode(sum%10);
            tail = tail.next;
        }
        carry = Math.floor(sum/10);
        if(l1)
            l1 = l1.next;
        if(l2)
            l2 = l2.next;
    }
    if(carry>0)
        tail.next = new ListNode(carry);
    return head;
}

链表相加II[与上一题的不同在于此题相加是按照数字相加的顺序来加的]

链接：

链表相加

描述：

1
2
3
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例：

链表相加

思路：

​ 先反转链表使得两个链表可以从头开始相加，然后再将结果链表反转

解法：

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
function reverse(head){
    let pre = null;
    let cur = head;
    while(cur){
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}
function addInList( head1 ,  head2 ) {
    // write code here
    let cur1 = reverse(head1);
    let cur2 = reverse(head2);
    let head = tail = null;
    let carry = 0;
    while(cur1||cur2){
        let val1 = cur1?cur1.val:0;
        let val2 = cur2?cur2.val:0;
        let val = val1+val2+carry;
        if(!head){
            head = new ListNode(val%10);
            tail = head;
        }else{
            tail.next = new ListNode(val%10);
            tail = tail.next;
        }
        carry = Math.floor(val/10);
        if(cur1)
            cur1 = cur1.next;
        if(cur2)
            cur2 = cur2.next;
    }
    if(carry){
        tail.next = new ListNode(carry);
        tail = tail.next;
    }
    return reverse(head);
}

合并两个有序链表[需要哑节点]

描述：

1
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

linklist

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var mergeTwoLists = function(l1, l2){
    const prehead = new ListNode(-1);
    let prev = prehead;
    while(l1&&l2){
        if(l1.val<l2.val){
            prev.next = l1;
            l1 = l1.next;
        }else{
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    prev.next = l1?l1:l2;
    return prehead.next;
}

删除排序链表中的重复元素II

描述：

1
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例：

删除重复元素

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var deleteDuplicates = function(head){
    if(!head)
        return head;
    var dummy = new ListNode(0, head);
    let cur = dummy;
    while(cur.next && cur.next.next){
        if(cur.next.val === cur.next.next.val){
            let val = cur.next.val;
            while(cur.next&&cur.next.val===val)
                cur.next = cur.next.next;
        }else
            cur = cur.next;
    }
    return dummy.next;
}

环形链表的约瑟夫问题

描述：

1
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

示例：

1
2
3
输入：5,2     
返回值：3    
说明：开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开.1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开.1，3，5，从5开始报数，5->1，1->2编号为1的人离开.3，5，从3开始报数，3->1，5->2编号为5的人离开.最后留下人的编号是3 .

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function ysf( n ,  m ) {
    // write code here
    let head = new ListNode(1);
    let tail = head;
    for(let i=2;i<=n;i++){
        tail.next = new ListNode(i);
        tail = tail.next;
    }
    tail.next = head;
    let cur = head;
    let pre = tail;
    let k = 0;
    while(cur.next&&cur.next!==cur){
        k++;
        let temp = cur.next;
        if(k===m){
            pre.next = temp;
            k=0;
        }
        pre = cur;
        cur = temp;
    }
    return cur.val;
}

​ 需要哑节点：移除链表元素、两两交换链表中的节点、删除倒数第N个节点。一般来说，需要哑节点的都是头节点可能发生变动的，为了使头节点的操作与其他节点的操作保持一致而添加哑节点。