Day7 25/2/20 THU

【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/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;
}