数据结构与算法 -- LeetCode中关于链表相关的算法题1
1 链表深拷贝
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
解题思路
首先需要对深拷贝有一个理解，所谓“深拷贝”与“浅拷贝”的区别在于，浅拷贝只是值传递，而深拷贝涉及到了引用传递，如果只是普通链表，只需要遍历一次，拿到旧节点的值之后，创建新的Node节点。 而本题中不同之处在于，每个节点多了一个随机指针，能够指向链表中的任意一个节点。
输入： head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出： [[7,null],[13,0],[11,4],[10,2],[1,0]]
这时候，如果仅仅是遍历链表是无法完成深拷贝的，因为在遍历的过程中，某个节点的random节点可能还没有创建，因此无法通过简单的遍历完成深拷贝。
方案1：哈希表
首先，先遍历一次链表，此时仅仅完成旧节点的深拷贝即可，每个节点的next节点与random节点先不需要关心，通过哈希表完成旧节点与新节点的映射关系。
// 旧的code对应新的code
Map<Node,Node> map = new HashMap();
Node temp = head;
//先遍历一次链表，将旧的节点对应的新的节点放在map里
while(temp != null){
map.put(temp,new Node(temp.val));
temp = temp.next;
}
此时我们中间可能任何使用到的节点都在map中，所以需要再遍历一次链表，完成新节点的next和random节点赋值工作即可。
这里我们需要记住一点，看下图：
7'是旧节点7的深拷贝节点，它的next节点其实就是旧节点7的下一个节点13的拷贝节点13'，那么怎么获取到13'节点，当前遍历的节点为7，其实从map中通过7的next节点就能拿到13对应的拷贝节点。
那么random节点如何获取呢，其实也一样，获取当前节点的random节点，从map中取到对应的拷贝节点即可。
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// 旧的code对应新的code
Map<Node,Node> map = new HashMap();
Node temp = head;
//先遍历一次链表，将旧的节点对应的新的节点放在map里
while(temp != null){
map.put(temp,new Node(temp.val));
temp = temp.next;
}
//注意此时map中，新节点的next和random都没有
temp = head;
//再从头遍历一次
while(temp != null){
//拿到新节点
Node newNode = map.get(temp);
//设置新节点的next = 旧节点的next
newNode.next = map.get(temp.next);
//设置新节点的random = 旧节点的random
newNode.random = map.get(temp.random);
temp = temp.next;
}
//拿到头结点的全部克隆节点
return map.get(head);
}
因为会遍历两次链表，时间复杂度为O(n)，n为链表长度；额外创建了Map，空间复杂度O(n).
链表合并与拆分
如果我们想要把map去掉，只从链表本身出发，从而使用一种O(1)的空间复杂度，这其实是一种优化手段，map的作用是什么，帮助我们快速找到想要的旧节点的拷贝节点。 其实如果我们制定一套规则，按照我们的规则去查找对应的节点，是可以抛弃哈希表的。
假设我们现在使用这样的规则：
当遍历到某个节点时，创建其克隆节点，放在当前节点与下一个节点中间，最终在原先节点的基础上长度变为一倍。
Node temp = head;
//按照规则生成新的链表 a-a'-b-b'-c-c''
while (temp != null) {
//创建clone节点
Node node = new Node(temp.val);
//拿到当前节点的下一个节点
Node nextNode = temp.next;
temp.next = node;
node.next = nextNode;
//此时因为有个中间节点，因此需要跳2步。
temp = temp.next.next;
}
接着我们遍历这个新链表，从head开始，我们先找到所有克隆节点的random节点，其实也很简单，我们在遍历新链表的时候，一组一组地遍历，对于clone节点的ramdom节点，其实就是旧节点的random节点的下一个节点，因为是按照我们的规则来的，所以一定是这样的，这样其实就是起到了哈希表的作用。
//此时先不需要关心clone节点的next节点，先把random连起来。
temp = head;
while (temp != null) {
//旧节点
Node oldNode = temp;
//克隆节点
Node newNode = temp.next;
//克隆节点的random节点，就是旧节点的random节点的下一个节点
newNode.random = oldNode.random == null ? null : oldNode.random.next;
//一组一组遍历
temp = temp.next.next;
}
这样其实就是把每个clone节点的random节点全部配置完成，然后再把全部的clone节点从新链表中拿出来即可。
public static Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node temp = head;
//按照规则生成新的链表 a-a'-b-b'-c-c''
while (temp != null) {
//创建clone节点
Node node = new Node(temp.val);
//拿到当前节点的下一个节点
Node nextNode = temp.next;
temp.next = node;
node.next = nextNode;
//此时因为有个中间节点，因此需要跳2步。
temp = temp.next.next;
}
//此时先不需要关心clone节点的next节点，先把random连起来。
temp = head;
while (temp != null) {
//旧节点
Node oldNode = temp;
//克隆节点
Node newNode = temp.next;
//克隆节点的random节点，就是旧节点的random节点的下一个节点
newNode.random = oldNode.random == null ? null : oldNode.random.next;
//一组一组遍历
temp = temp.next.next;
}
//现在想怎么拆分
temp = head;
//
Node res = null;
Node tail = null;
while (temp != null) {
if (res == null) {
tail = res = temp.next;
} else {
res.next = temp.next;
res = res.next;
}
temp = temp.next.next;
}
return tail;
}
其实这道题几乎把链表中能出题的点都涵盖了，算是比较难的一道题了。
链表反转
链表翻转是经典的面试题，常见的就是单链表的反转，常见的思路是构建一个空链表，在遍历链表的同时，改变节点的指向。
//改变head的指向
ListNode next = head.next;
head.next = pre;
改变方向之后，往下遍历下一个节点。
pre = head;
head = next;
如此往复，最终pre移动到最后一个节点6之后，遍历结束，返回pre即可。
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
//这个链表就是新节点的头结点
ListNode pre = null;
while(head != null){
//获取当前节点的下一个节点
ListNode next = head.next;
//开始翻转
head.next = pre;
//pre要往上走到当前节点，下一个节点的next指针要指向pre
pre = head;
head = next;
}
return pre;
}
那么中等难度的题目，则是会在某个区间内反转链表，如下：
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
输入： head = [1,2,3,4,5], left = 2, right = 4
输出： [1,4,3,2,5]
解题思路
因为是在区间内的反转，而且链表无法像数组一样，通过双指针来完成反转，但是通过下面的图可以看到整体的规则：
假设要反转第2到第4个元素，那么最终拿到的链表是:
其实思路就比较清晰了，第left-1个元素指向第right个元素，第left个元素指向第right+1个元素，中间的元素做链表翻转。
所以在此之前，需要准备好几个变量：开始反转时的变量leftNode，其之前的变量preLeftNode，结束反转时的变量rightNode以及其下一个节点r1.
public ListNode reverseBetween(ListNode head, int left, int right) {
//这道题是翻转一定区间的链表
if(head == null){
return null;
}
if(left > right){
return null;
}
if(left == right){
return head;
}
//首先找到起始节点和终点，遍历一次链表
ListNode dummy = new ListNode(-1);
dummy.next = head;
//找到left和right坐标对应的节点
//记住一点 left是开始反转的起始节点，还需要找到left的前一个节点
//因为开始反转的位置，很可能是第一个，因此使用dummy创建了一个虚拟节点
ListNode preLeftNode = dummy;
for(int i = 0;i<left-1;i++){
preLeftNode = preLeftNode.next;
}
ListNode leftNode = preLeftNode.next;
ListNode tail = preLeftNode.next;
//找到右边节点
ListNode rightNode = dummy;
for(int i = 0;i<right;i++){
rightNode = rightNode.next;
}
//找到right节点的下一个节点
ListNode r1 = rightNode.next;
rightNode.next = null;
//开始反转
ListNode pre = null;
while(leftNode != null){
ListNode next = leftNode.next;
leftNode.next = pre;
pre = leftNode;
leftNode = next;
}
//拼接链表
preLeftNode.next = pre;
tail.next = r1;
return dummy.next;
}
链表删除节点
对于链表节点的删除，常规的方式通过遍历链表，拿到下个节点判断是否可以删除，如果删除，就将当前节点的下个节点指向下个节点的下个节点。
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while(cur.next != null){
//拿到下个节点
ListNode next = cur.next;
if(next.val == val){
cur.next = next.next;
}else{
cur = cur.next;
}
}
return dummy.next;
}
这个也只能说是最简单的删除节点的题目了，接下来来点难度的。
问题1 删除链表中倒数第n个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
其实这道题目，它让我们删除倒数第n个节点，我们需要按照正向思维来看，其实就是删除正数第length - n + 1个节点。
首先我们先遍历链表拿到链表的长度。
int length = 0;
ListNode dummy = new ListNode(-1,head);
ListNode left = dummy.next;
while(left != null){
left = left.next;
length++;
}
既然要删除目标节点，首先就需要3个成员变量，目标节点的前一个节点pre，需要删除的节点cur，以及目标节点的下一个节点next，所以需要再遍历一次链表。因为删除的元素很有可能是第一个，所以我们在构建dummy的时候，新加了一个虚拟节点 ，因此在遍历的时候，我们
//需要删除第 length - n + 1个节点
int pos = 1;
//如果删除的是第一个元素，就需要用这个虚拟节点
ListNode pre = dummy;
while(pos < length - n + 1){
pre = pre.next;
pos++;
}
ListNode cur = pre.next;
ListNode next = cur == null ? null : cur.next;
pre.next = next;
假如链表长度为5，需要删除倒数第2个元素，其实就是删除正数第（5-2+1）=4个元素，所以在遍历的时候，首先取到目标节点的前一个节点pre，后续就正常拿到其他的两个变量，做对应的指针指向即可。
public ListNode removeNthFromEnd(ListNode head, int n) {
//题目给你反的操作，我们按照正向思维来看
//删除倒数第n个节点，其实就是删除正数第 length - n +1 个节点
int length = 0;
ListNode dummy = new ListNode(-1,head);
ListNode left = dummy.next;
while(left != null){
left = left.next;
length++;
}
//需要删除第 length - n + 1个节点
int pos = 1;
//如果删除的是第一个元素，就需要用这个虚拟节点
ListNode pre = dummy;
while(pos < length - n + 1){
pre = pre.next;
pos++;
}
ListNode cur = pre.next;
ListNode next = cur == null ? null : cur.next;
pre.next = next;
return dummy.next;
}
问题2 删除链表中的重复元素
给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。
输入： head = [1,2,3,3,4,4,5]
输出： [1,2,5]
这个问题也是中等难度的问题，我们先看具体的要求是主要是重复的元素都要全部删除，那么其实重复的元素很有可能在第一个，因此也需要构建虚拟节点。
因此在遍历链表的时候，至少需要两个变量，当前节点（一定不是重复元素）cur的下个节点和下下个节点，如果这两者重复，那么就需要一直往下找，直到找到不重复的元素，当前节点的下一个节点指向它。仅仅是指向它，并不代表当前节点要移动到这个节点，还需要在while循环中，判断这个节点与其下一个节点是否重复。
如果两者不重复，那么就遍历下个节点，为啥不能直接跳到下下个节点？是因为下下个节点很有可能是和它下个节点是重复节点。
public ListNode deleteDuplicates(ListNode head) {
//因为是排序的，所以不要考虑之前是否有重复元素
if(head == null || head.next == null){
return head;
}
//如果两个元素重复，还是有可能出现在第一个元素的位置，因此还需要虚拟节点
ListNode dummy = new ListNode(-1,head);
//当前节点
ListNode cur = dummy;
while(cur.next != null && cur.next.next != null){
//当前节点的下一个节点
ListNode node1 = cur.next;
//当前节点的下下个节点
ListNode node2 = cur.next.next;
if(node1.val != node2.val){
//继续往下走了
cur = cur.next;
}else{
//如果当前节点与下个节点的值一样，那么循环，一直找到不一样的节点
while(node2 != null && node2.val == node1.val){
node2 = node2.next;
}
//出来了，此时next的值，与是不同的
//将cur的指针直接指向不同值的位置即可。
cur.next = node2;
}
}
return dummy.next;
}
这里有一点需要记住，但凡涉及到了节点取值，一定要在此之前判空！