链表还是没啥数据概念，多做做点题目，理解理解链表

反转链表

题目

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
    14
    15
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
        let current = head
        let pre = null
        while(current) {
            const next = current.next
            current.next = pre
            pre = current
            current = next
        }
        return pre
    };

两两交换链表中的节点

题目

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1

两两交换

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

示例 1

输入：head = [1]
输出：[1]

思路

对于不熟悉链表数据结构的同学还是画画流程图，图画好了基本能明白大概了

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 两两交换
swapPairs() {
  const head = this.head
  if (!head) return null;
  let helper = function(node) {
    const tempNext = node.next
    if (tempNext) {
      const tempNextNext = node.next.next
      node.next.next = node
      if (tempNextNext) {
        node.next = helper(tempNextNext)
      } else {
        node.next = null
      }
    }
    return tempNext || node
  }
  this.head = helper(head);
  console.log('head', this.head);
  // return res
}

代码位置 链表问题1

参考

环形链表一

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例1

两两交换

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

解法1 hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hasCycle() {
  let current = this.head
  if (!current || !current.next) {
    return false
  }
  let map = new Map();
  while(current.next !== null) {
    if (map.has(current)) {
      return true
    }
    map.set(current, true)
    current = current.next
  }
  return false
}

解法2 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
var hasCycle = function(head) {
    let current = head
    const arr = [];
    while(current !== null) {
      if (arr.includes(current)) {
        return true
      } else {
        arr.push(current)
      }
      current = current.next
    }
    return false
};

解法3 快慢指针

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

参考链接

环形链表二

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例1

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解法1 hash

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 detectCycle = function(head) {
    let current = head
    if (!current || !current.next) {
      return null
    }
    let map = new Map();
    while(current !== null) {
      if (map.has(current)) {
        return current
      }
      map.set(current, true)
      current = current.next
    }
    return null
};

解法2快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function (head) {
    let fast = head,
        slow = head;

    // 快慢指针确定有环
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;

        // 确定有环，开始找环的第一个节点
        if (fast === slow) {
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
};

参考链接