从尾到头打印链表

Easy 原题连接：剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

示例：

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

提示：

0 <= 链表长度 <= 10000

解题思路

从尾到头输出，也就是遍历，时间复杂度最小为O(n)，那么空间复杂度越小越好

首先想到的是反转链表，空间复杂度为O(1)，时间复杂度O(n)

反转列表需要三个Node变量，记录上一个节点方便向前连接，记录当前节点用于改变next、指向第一个节点代表的前节点、记录原本的后续节点

先记录下一个节点的信息，再将next指向前节点，以此类推，反转链表

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[0];
        ListNode a1 = head;
        ListNode a2 = head.next;
        ListNode a3 = head;
        int s1 = 1;

        while(a2!=null){
            a3 = a2.next;
            a2.next = a1;
            a1 = a2;
            a2 = a3;
            s1++;
        }

        int[] arr = new int[s1];
        for(int i=0; i<s1; i++){
            arr[i] = a1.val;
            a1 = a1.next;
        }
        return arr;
    }
}

反转链表

Easy 原题连接：反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

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

提示：

0 <= 节点个数 <= 5000

解题思路

同第一题思路

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //处理边界条件
        if(head == null || head.next == null) return head;
        //记录后续指针和
        ListNode n1 = head, n2 = head, n3 = null;
        while(n1 != null){
            n1 = n2.next;
            n2.next = n3;
            n3 = n2;
            n2 = n1;
        }
        return n3;
    }
}

复杂链表的复制

medium 原题连接：剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
    
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
    
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

  • -10000 <= Node.val <= 10000
  • Node.random 为空（null）或指向链表中的节点。
  • 节点数目不超过 1000 。

解题思路

这个问题同样涉及遍历列表，所以时间复杂度最低为O(n)，那么空间复杂度越低越好，而空间适用问题在于存储链表节点信息

可以考虑适用HashMap<Node, Node>存储原值和复制值，再依次get传递random连接

又或者直接复制节点在源节点后，遍历三次：

第一次创建复制节点并后接：1 - 1copy - 2 - 2copy - 3 - 3copy-… （复制当前节点以存储后继节点，当前节点指向复制节点，节点调制复制节点的后继节点）

第二次连接对应的random链接 （复制节点获得当前节点的random所指的节点的后继节点，即复制节点指向复制random）

第三次拆开链表：1 - 2 - 3 - .. 1copy - 2copy - 3copy - .. （每个节点都指向后继的后继）

Java代码

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        // 判空
        if(head == null) return head;
        // 1. 复制链表在原节点后: 1-1`-2-2`-3-3-...
        Node mid, copy;
        for(mid = head; mid != null; mid = copy.next) {
            copy = new Node(mid.val);
            copy.next = mid.next;
            mid.next = copy;
        }
        // 2. 复制节点的random连接
        for(mid = head; mid != null; mid = mid.next.next) {
            copy = mid.next;
            if(mid.random != null) {
                copy.random = mid.random.next;
            }
        }
        // 3. 分离链表: 1-2-3-..  1`-2`-3`-..
        Node copyList = head.next;
        for(mid = head; mid.next != null;) {
            copy = mid.next;
            mid.next = copy.next;
            mid = copy;
        }
        return copyList;
    }
}