数据结构与算法 — 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;
}

这儿有一点需求记住，凡是涉及到了节点取值，必定要在此之前判空！