Day725/2/20THU

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】 .bilibili /video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358

目录

4、链表

4.3 链表的习题

4.3.1 例1

4.3.2 例2及其进阶问题

4.3.3 例3

---

笔记：

4、链表 4.3 链表的习题 4.3.1 例1

【例1：反转链表的代码实现】

分别实现反转单向链表、反转双向链表。要求链表长度为N，时间复杂度O(N)，额外空间复杂度O(1)。

反转单向链表：

struct Node { int value; Node *next; Node(int data){ value = data; } }; static Node *reverseList(Node *head){ Node *pre = nullptr; Node *next = nullptr; while (head != nullptr) { next = head->next; head->next = pre; pre = head; head = next; } return pre; }

 

反转双向链表：

struct DoubleNode{ int value; DoubleNode *last; DoubleNode *next; DoubleNode(int data){ value = data; } }; static DoubleNode *reverseDoubleList(DoubleNode *head){ DoubleNode *pre = nullptr; DoubleNode *next = nullptr; while (head != nullptr) { next = head->next; head->next = pre; head->last = next; pre = head; head = next; } return pre; }

4.3.2 例2及其进阶问题

【例2：按数值大小划分单向链表】

给定单链表的头节点head，节点的值类型时整型，再给定一个整数pivot。实现一个函数，将单向链表按某值划分为左边的值小于pivot、中间等于pivot、右边大于pivot的形式。

解法1（笔试，可用额外的数据结构）：把每个节点放进数组中，用partition排好序。再串成节点。

解法2（面试，只用有限的变量搞定）：6个指针分别处理小于、等于、大于区域的头和尾。再把三个区域串在一起。

无论原始链表有多少个节点，都只需要额外的6个指针就能处理。假设小于区域S、等于区域E、大于区域B的头尾节点分别为sHead、sTail、eHead、eTail、bHead、bTail，初始值都为null。

如图所示，遍历原链表，第一个值为4，小于5，sHead=4，sTail=4；遍历到6的时候bHead=6，bTail=6。遍历到3的时候，小于区域的指针已经不是null了，就让sTail=3。

这个方法只能保证链表按小于、等于、大于pivot被分为三个区域，区域内顺序能确保稳定性但不一定是有序的。

最后需要注意的是，如果没有小于pivot的区域、等于pivot的区域、大于pivot的区域，连接时一定要注意边界，空指针的next指针会报错，所以要分情况讨论。

进阶思考题：

进阶1：调整后，所有小于pivot的节点之间的相对顺序和调整前一样。

进阶2：调整后，所有等于pivot的节点之间的相对顺序和调整前一样。

进阶3：调整后，所有大于pivot的节点之间的相对顺序和调整前一样。

进阶4：时间复杂度O(N)，额外空间复杂度O(1)。

4.3.3 例3

【例3：复制含有随机指针节点的链表】

一种特殊的单链表节点类描述如下：

class Node{ int value; Node next; Node rand; Node(int val){ value = val; } }

rand指针是单链表结构中新增的指针，可能指向链表中任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。

要求时间复杂度O(N)，额外空间复杂度O(1)。

解法1（适合笔试时答）：

解法2（适合面试时答）：不用表，只用有限变量的方式。

利用克隆节点分离新、旧表

public static Node copyListWithRand2(Node head){ if(head == null) return null; Node cur = head; Node next = null; // copy node and link to every node // 1 -> 2 // 1 -> 1' -> 2 while(cur != null){ nexr = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; Node curCopy = null; // set copy node rand // 1 -> 1' -> 2 -> 2' while(cur != null){ next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } Node res = head.next; cur = head; //split while(cur != null){ next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } return res; }