算法随笔 — 线性表基础 — 链表

今天药忘吃喽~ 2022-11-06 03:00 133阅读 0赞

## 单链表是什么 ##

已经熟悉单链表概念的读者可以跳至单链表的实现或习题。

链表和数组很像，它们都是线性的存储结构，它们的不同点是数组是用一段连续的内存地址来存储数据，这也是为什么数组可以通过下标来直接访问的原因。

链表是相对松散的线性结构，也就是说链表中每个节点的物理地址可能不是连续的。

数组读取数据的时间复杂度是O(1)，而链表则是O(n)，因为要访问链表的某个节点必须从头开始遍历。

链表中的一个节点可以分为两部分：指针域和数据域。

指针域是用来指向下一个节点的位置，而数据域则是用来存储这个节点表示的数据。

![单链表][20210308084428200.png_pic_center]  
**链表常用场景**

1.  操作系统内的动态内存分配 (一种实现方式)
2.  LRU 缓存淘汰算法
3.  …

--------------------

## 单链表的实现 ##

单链表的实现方式主要有两种，通过对象引用的方式和数组方式

### 1.对象形式 ###

class ListNode { 
      val: any
      next: ListNode | null
      constructor(val: any, next: ListNode) { 
        this.val = val === undefined ? 0 : val
        this.next = next === undefined ? null : next
      }
    }
    
    function checkChain(head: ListNode) { 
      let result = ''
      while (head) { 
        result += head.val + '->'
        head = head.next
      }
      console.log(result)
    }
    
    // main
    const head = new ListNode(0, null)
    const node1 = new ListNode(1, null)
    const node2 = new ListNode(2, null)
    const node3 = new ListNode(3, null)
    
    head.next = node1
    node1.next = node2
    node2.next = node3
    
    checkChain(head) // 0->1->2->3->

### 2.数组形式 ###

![通过双数组实现链表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center]

// @ts-ignore
    const data: number[] = new Array(10).fill(0)
    // @ts-ignore
    const next: number[] = new Array(10).fill(0)
    
    const add = (lastPointer: number, curPointer: number, val: number) => { 
      next[lastPointer] = curPointer
      data[curPointer] = val
    }
    
    // main
    //* 定义头节点
    const head = 3
    data[3] = 0
    
    //* 添加后续节点
    add(3, 5, 1)
    add(5, 2, 2)
    add(2, 7, 3)
    add(7, 9, 100)
    
    //* 遍历链表
    let p = head
    let result = ''
    while (p !== 0) { 
      result += `${ data[p]}->`
      p = next[p]
    }
    console.log(result)	// 0->1->2->3->100->

--------------------

## 习题 ##

以下是在LeetCode上有关单链表的习题，有条件的读者可以边看边做。

只要是不看答案就写不出来的都不算是掌握了。

===================================

### leetCode 141 环形链表 ###

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

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

如果链表中存在环，则返回 true 。 否则，返回 false 。  
![leetCode141][]  
**解题思路:**  
使用快慢指针，慢指针每次走一步，快指针每次走两步，如果有环，两个指针迟早会指向同一个节点。

由于每次快指针都比慢指针多走一步，所以当两指针都进入环时，每走一次二者的距离都少1。

function hasCycle(head: ListNode | null): boolean { 
        if (!head || !head.next) return false
        let slow = head, fast = head
        do { 
            slow = slow.next
            fast = fast.next.next
        } while (slow !== fast && fast && fast.next)
        return !!fast && !!fast.next
    };

![141][]

===================================

### leetCode 142 环形链表2 ###

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

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

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

![leetCode142][]  
**解题思路：**  
和上题类似，定义快慢指针，先找到二者相遇的节点

接着先给出一个结论，此时让慢指针回到链头，慢指针和快指针距离环的起点的距离是相等的

接下来解释这个结论是怎么得出的

![环形链表起点][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center 1]  
结合上图所给条件，又知快指针的步长是慢指针的两倍，所以  
 2 ( a + b ) = a + b + n ( b + c ) a = ( n − 1 ) b + n c a = ( n − 1 ) ( b + c ) + c ∵ ( n − 1 ) 为 圈 数 ， 直 接 忽 略 不 计 ∴ a = c 2(a+b)=a+b+n(b+c)\\\\ a=(n-1)b+nc\\\\ a=(n-1)(b+c)+c\\\\ \\because (n-1)为圈数，直接忽略不计\\\\ \\therefore a = c 2(a\+b)=a\+b\+n(b\+c)a=(n−1)b\+nca=(n−1)(b\+c)\+c∵(n−1)为圈数，直接忽略不计∴a=c

有了以上结论之后解题步骤就清晰了

1.  找到快慢指针的相遇点(和上题一样的做法)
2.  让慢指针回到链头
3.  让快慢指针以每次单位1的步长前进，直到二者相遇为止

function detectCycle(head: ListNode | null): ListNode | null { 
    	if (!head || !head.next) return null
    	//* 1.先找到相遇点
    	let slow = head, fast = head
    	do { 
    		slow = slow.next
    		fast = fast.next.next
    	} while (slow !== fast && fast && fast.next)
    	if (!fast || !fast.next) return null
    	//* 2.让慢指针回到链头
    	slow = head
    	//* 3.使两指针步长都为1，当两指针相遇时即为链环的起点
    	while (slow !== fast) { 
    		slow = slow.next
    		fast = fast.next
    	}
    	return fast
    };

![142][]

===================================

### leetCode 202 快乐数 ###

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。  
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。  
如果 可以变为 1，那么这个数就是快乐数。  
如果 n 是快乐数就返回 true ；不是，则返回 false

输入：19
    输出：true
    解释：
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

输入：n = 2
    输出：false

**解题思路：**  
其实快乐数就是一个判断链表是否有闭环的问题，当有闭环时说明这个数不是快乐数，否则就是。

所以解题思路和 leetCode 141 题是一样的。

function isHappy(n: number): boolean { 
    	let slow = n, fast = n
    	do { 
    		slow = getNext(slow)
    		fast = getNext(getNext(fast))
    	} while (slow !== fast && fast !== 1)
    	return fast === 1
    }
    function getNext(num: number) { 
    	return String(num).split('').reduce((sum, cur) => sum + Math.pow(Number(cur), 2), 0)
    }

![202][]  
当然，如果笔者使用的是js的话，`getNext()`可以写作

function getNext(num) { 
    	return String(num).split('').reduce((sum, cur) => sum + cur * cur, 0)
    }

因为两个操作数进行 \* 操作的时候会将二者隐式类型转换为数字类型

===================================

### leetCode 206 反转链表 ###

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

**解题思路：**  
本题有两个解法：三指针和递归

先说三指针：

1.  定义三个指针，pre cur next
2.  初始 pre 指向 null， cur 指向头节点，next指向头节点的下一节点
3.  以 cur 为参考开始遍历整个链表，每次遍历操作如下
    
    1.  cur 指向 pre
    2.  pre 移动到 cur 所处节点
    3.  cur 移动到 next 所处节点
    4.  next 移动到 next 的下一节点

function reverseList(head: ListNode | null): ListNode | null { 
        if (!head || !head.next) return head
        let pre = null, cur = head, next = head.next
        while (cur) { 
            cur.next = pre
            pre = cur
            cur = next
            if (next) next = next.next
        }
        return pre
    };

![206-1][]

递归：

递归的真谛就是甩锅，自己做不到的事就交给别人做，每次(每个作用域)只解决一个具体的问题

在本题中，每次作用域要做的事情就是将下一节点指向自己，最后返回反转后的头节点

以笔者的文字功底，很难将递归描述清楚，所以接下来我会先给出代码，再把图画出，至于能不能看懂，就要看你的悟性了

function reverseList(head: ListNode | null): ListNode | null { 
      if (head === null || head.next === null) return head
      const tail = head.next, p = reverseList(head.next)
      head.next = tail.next
      tail.next = head
      return p
    }

![206-2][]  
![反转链表1][1]  
![反转链表2][2]

===================================

### leetCode 92 反转链表II ###

反转从位置m到n的链表。请使用一次遍历完成反转。

1 ≤ m ≤ n ≤ 链表长度
    输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

**思路分析：**  
由于本题可能会对链头进行操作，因此需要插入虚拟头节点

![反转区间节点链表2][2 1]

1.  插入虚拟头节点
2.  令指针P指向第一个待反转节点的前一位
3.  利用上题的方式进行反转链表，注意次数为 n - m + 1
4.  将指针P指向反转链表后的头节点

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null { 
    	if (!head || !head.next) return head
    	const virtualHead = new ListNode(null, head)
    	let p = virtualHead
    	const cnt = right - left + 1
    	// 使p指针移动到第一个待反转节点的前一个节点
    	while (--left) { 
    		p = p.next
    	}
    	// 开始反转节点，并使p的next指向反转后链表的头节点
    	p.next = reverseN(p.next, cnt)
    	return virtualHead.next
    };
    
    function reverseN(node: ListNode | null, cnt: number): ListNode | null { 
    	if (cnt === 1) return node
    	const tail = node.next
    	const p = reverseN(node.next, cnt - 1)
    	node.next = tail.next
    	tail.next = node
    	return p
    }

![92][]

===================================

### leetCode 25 K个一组反转链表 ###

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

**进阶：**

1.  你可以设计一个只使用常数额外空间的算法来解决此问题吗？
2.  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

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

**解题思路：**

1.  原链表插入虚拟头节点，并定义p、q两个指针  
    ![25题解][25]  
    p 指向待操作组的头节点的前一位  
    q 指向待操作组的头节点
2.  每次在反转链表前先让q指针判断待操作组数量够不够n个
    
    1.  够，执行反转链表操作
    2.  不够，返回传入头节点
3.  当进行了链表反转操作后，q指针 指向了反转后链表的尾节点，此时让 p指针 移动到 q指针 的位置，q指针移向下一位

function reverseKGroup(head: ListNode | null, k: number): ListNode | null { 
    	if (head === null || head.next === null) return head
    	const virtualHead = new ListNode(0, head)
    	let p = virtualHead, q = head
    	while ((p.next = reverseN(q, k)) !== q) {  // 该条件成立说明执行了反转操作
    		p = q
    		q = q.next
    	}
    	return virtualHead.next
    };
    
    function reverseN(node: ListNode, n: number): ListNode { 
    	let p = node
    	const cnt = n
    	while (--n && p) p = p.next
    	if (p === null) return node // 不足n个
    	return _reverseN(node, cnt)
    }
    
    function _reverseN(node: ListNode, n: number): ListNode { 
    	if (n === 1) return node
    	const tail = node.next,
    		p = _reverseN(node.next, n - 1)
    	node.next = tail.next
    	tail.next = node
    	return p
    }

![25][25 1]

===================================

### leetCode 61 旋转链表 ###

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2
    输出: 4->5->1->2->3->NULL
    解释:
    向右旋转 1 步: 5->1->2->3->4->NULL
    向右旋转 2 步: 4->5->1->2->3->NULL
    
    输入: 0->1->2->NULL, k = 4
    输出: 2->0->1->NULL
    解释:
    向右旋转 1 步: 2->0->1->NULL
    向右旋转 2 步: 1->2->0->NULL
    向右旋转 3 步: 0->1->2->NULL
    向右旋转 4 步: 2->0->1->NULL

**解题思路：**

1.  定义 指针p 指向头节点，遍历到尾节点，然后使尾节点指向头节点形成闭环
2.  令链表长度为L，使 指针p 走 L-(k % L) 步
3.  此时，指针p 所指位置为新链表的尾节点，所指的后一位为新链表的头节点  
    ![旋转链表题解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center 2]  
    循环右移时指针移动步数: L - (k % L)  
    循环左移时指针移动步数: k % L (模仿上图自行推断)

function rotateRight(head: ListNode | null, k: number): ListNode | null { 
    	if (head === null || head.next === null || !k) return head
    	let p = head, length = 1
    	while (p.next !== null) { 
    		p = p.next
    		length++
    	}
    	p.next = head
    	let cnt = length - (k % length)
    	while (cnt--) p = p.next
    	const newHead = p.next
    	p.next = null
    	return newHead
    };

![61][]

===================================

### leetCode 24 两两交换链表中的节点 ###

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

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

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

**解题思路：**  
这题就是上述 leetCode 25 的一个特殊案例，在那道题中令 k = 2 即可得到这道题的答案。

具体过程就不再复述了，不清楚的同学可以回到上面重新学习。

function swapPairs(head: ListNode | null): ListNode | null { 
        if (!head || !head.next) return head
        const virtualHead = new ListNode(null, head)
        let p = virtualHead, q = head
        while ((p.next = reverseN(q, 2)) !== q) { 
            p = q
            q = q.next
        }
        return virtualHead.next
    };
    
    function reverseN (node: ListNode, n: number): ListNode { 
        const cnt = n
        let p = node
        while (--n && p) { 
            p = p.next
        }
        if (!p) return node
        return _reverseN(node, cnt)
    }
    
    function _reverseN (node: ListNode, cnt: number): ListNode { 
        if (cnt === 1) return node
        const tail = node.next
        const p = _reverseN(node.next, cnt - 1)
        node.next = tail.next
        tail.next = node
        return p
    }

![24][]

===================================

### leetCode 19 删除链表的倒数第n个节点 ###

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

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

**解题思路：**

链表要删除第n个节点，就要先找到第 n - 1 个节点在哪

使用双指针法就能很快解出本题

1.  往原链表添加虚拟头节点 (因为有可能会变更头节点)
2.  定义慢指针指向虚拟头节点，快指针指向头节点
3.  快指针往后走n步
4.  快慢指针同时向后走，直到快指针到尾节点
5.  此时慢指针就到被删除节点的前一个节点了

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { 
        if (!head) return null
        const virtualHead = new ListNode(null, head)
        let slow = virtualHead, quick = head
        while (--n && quick.next) { 
            quick = quick.next
        }
        while (quick.next) { 
            slow = slow.next
            quick = quick.next
        }
        slow.next = slow.next.next
        return virtualHead.next
    };

![19][]

===================================

### leetCode 83 删除排序链表中的重复元素 ###

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

输入: 1->1->2
    输出: 1->2
    
    输入: 1->1->2->3->3
    输出: 1->2->3

**解题思路：**  
—— 快慢指针

1.  定义快慢指针同时指向头节点
2.  使快指针一直往后走，直到与慢指针代表的值不同
3.  使 慢指针的next 指向 快指针
4.  使慢指针移动到快指针的位置
5.  重复以上步骤直到慢指针到尾节点

function deleteDuplicates(head: ListNode | null): ListNode | null { 
        if (!head) return null
        let slow = head, fast = head
        while (slow) { 
            while (fast && slow.val === fast.val) { 
                fast = fast.next
            }
            slow.next = fast
            slow = fast
        }
        return head
    };

![83-1][]  
—— 单指针

1.  定义一个指针指向链头，遍历到链尾
2.  每次遍历的时候判断下一节点的val是否和当前节点的相等，如果不等使 当前节点的next 指向下下个节点

function deleteDuplicates(head: ListNode | null): ListNode | null { 
       if (head === null) return null
       let p = head
       while (p.next) { 
           if (p.val === p.next.val) { 
               p.next = p.next.next
               continue
           }
           p = p.next
       }
       return head
    };

![83-2][]

===================================

### leetCode 82 删除排序链表中的重复元素 ###

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

输入: 1->2->3->3->4->4->5
    输出: 1->2->5
    
    输入: 1->1->1->2->3
    输出: 2->3

**解题思路：**

1.  因为这题又有可能操作头节点，所以需要插入虚拟头节点
2.  剩下的解题思路和上题基本相似，但是这题只能用双指针，因为删除节点必须要找到被删除节点的前一个节点，在本题的情况下只能用双指针才更加方便

function deleteDuplicates(head: ListNode | null): ListNode | null { 
    	if (head === null || head.next === null) return head
    	const virtualHead = new ListNode(null, head)
    	let p = virtualHead, q = p
    	while (p.next) { 
    		if (p.next.next && p.next.next.val === p.next.val) { 
    			q = p.next.next
    			while (q && q.val === p.next.val) q = q.next
    			p.next = q
    			continue
    		}
    		p = p.next
    	}
    	return virtualHead.next
    };

![82][]

--------------------

## 结语 ##

创作不易，如果本文对你有帮助，请点一个免费的赞鼓励一下。如果本文有错误或者你有更好的想法，欢迎评论区评论~

[20210308084428200.png_pic_center]: /images/20221023/46861bd4ac5442c8966f3422d53e5e13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/1ccedbcf1a6d4820850d350e5cbcb94d.png
[leetCode141]: /images/20221023/95fa05f00c3848f1a88f861c1a33d5f4.png
[141]: /images/20221023/11e2d9ca2d7c40cc90dee8b530ac08dd.png
[leetCode142]: /images/20221023/c7e2946927684d73a6dfce907afd5066.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/7193af732c6e4e7dbca0d7f2f5a16fe6.png
[142]: /images/20221023/1624d46709d641f39402033b76670209.png
[202]: /images/20221023/a04ef837141d460ea7f7c8378c164991.png
[206-1]: /images/20221023/37df6a71733e4351a01ea3cc46a586ad.png
[206-2]: /images/20221023/00d36b987a904afc804f57babd311229.png
[1]: /images/20221023/4ca0f80a32cc478ca382d9596872f01e.png
[2]: /images/20221023/d1aba74669364223b58a0703ad42fe43.png
[2 1]: /images/20221023/4db94e1f50b1452ba946bf7b71fa0007.png
[92]: /images/20221023/bce19ee0efbf4456ae0b65212b28b35b.png
[25]: /images/20221023/735b09c8c4414dc29bb7f9c36785ecd4.png
[25 1]: /images/20221023/9e6c873a43d7495fafc69f5790600a31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/485744358be24930b65ea08af8b57e54.png
[61]: /images/20221023/449025c5a4e14e2c988b140f2542826c.png
[24]: /images/20221023/a93861051a594c088e157a3855472367.png
[19]: /images/20221023/429b030440b24aaa8c70f2947f77030f.png
[83-1]: /images/20221023/f80bf7b6587b484a843513008c62ec81.png
[83-2]: /images/20221023/c71cb9f14f894ec78a3bcc3aaea4896a.png
[82]: /images/20221023/d3c8a693d46c43e891ba794fd43e0b23.png