链表

1. 移除链表元素

203

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

通过创建虚拟头结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    let dummy=new ListNode(0)
    dummy.next=head
    let cur=dummy
    if(!head){
        return head
    }
    while(cur.next){
        if(cur.next.val==val){
            cur.next=cur.next.next
        }else{
            cur=cur.next
        }
        
    }
    return dummy.next
};

2. 设计链表

707 难

1
2
3
4
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

3. 反转链表

206

双指针：

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head){
        return head
    }
    let pre=null
    let cur=head
    let temp
    while(cur){
        temp=cur.next
        cur.next=pre
        pre=cur
        cur=temp
    }
    return pre
};

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    return reverse(head,null)
};
const reverse=(cur,pre)=>{
    if(!cur){
        return pre
    }
    let temp=cur.next
    cur.next=pre
    return reverse(temp,cur)
}

4. 两两交换链表中的节点

24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
 let dummy = new ListNode()
  dummy.next = head
  let current = dummy
  while (current.next !== null && current.next.next !== null) {
    let n1 = current.next
    let n2 = current.next.next
    n1.next = n2.next
    current.next = n2
    n2.next = n1
    current = n1
  }
  return dummy.next
};

5. 删除链表中倒数第n个节点

19

由于我们需要找到倒数第 nnn 个节点，因此我们可以使用两个指针 first和 second同时对链表进行遍历，并且 first比 second超前 nnn 个节点。当 first\textit{first}first 遍历到链表的末尾时，second就恰好处于倒数第 n 个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let dummy=new ListNode()
    dummy.next=head
    let p1=dummy
    let p2=dummy
    while(n){
        p2=p2.next
        n--
    }
    while(p2.next){
        p1=p1.next
        p2=p2.next
    }
    p1.next=p1.next.next
    return dummy.next
};

6. 环形链表II

142

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 *如果链表无环，则返回 null。

1.用哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let hash=new Set()
    while(head!==null){
        if(hash.has(head)){
            return head
        }
        hash.add(head)
        head=head.next
    }
    return null
};