「剑指Offer」Day02：链表（简单）

剑指 Offer 06. 从尾到头打印链表

题目描述

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

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

输出：[2,3,1]

题目链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

方法一：借助ArrayList的头插法

/**
 * 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];
        }
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(0, head.val); //借助ArrayList，使用头插法
            head = head.next;
        }
        int length = list.size();
        int[] res = new int[length];
        for(int i = 0; i < length; i++){ //将集合中结果输出到数组
            res[i] = list.get(i);
        }
        return res;
    }
}

方法二：递归

后序遍历，先递归到链表的末尾，在回溯过程中将节点值存入集合中

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[0];
        }
        List<Integer> list = postOrder(head, new ArrayList<Integer>());
        int[] res = new int[list.size()];
        int index = 0;
        for(int val : list){ //将集合中结果输出到数组
            res[index++] = val;
        }
        return res;
    }
    public ArrayList<Integer> postOrder(ListNode head, ArrayList<Integer> list){ //后序遍历
        if(head == null){
            return list;
        }
        list = postOrder(head.next, list);
        list.add(head.val);
        return list;
    }
}

方法三：栈

能够使用递归的地方就能够用栈代替，先遍历入栈，再将值出栈到结果数组

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[0];
        }
        Stack<Integer> stack = new Stack<>();
        int size = 0;
        while(head != null){
            stack.push(head.val);
            size++;
            head = head.next;
        }
        int[] res = new int[size];
        int index = 0;
        while(!stack.isEmpty()){
            res[index++] = stack.pop();
        }
        return res;
    }
}

剑指 Offer 24. 反转链表

题目描述

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

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

题目链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

实现代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = head;
        while(head != null){
            next = head.next; //暂存当前节点的下一个节点
            head.next = pre;  //当前节点指向前一个节点
            pre = head;       //前一个节点变为当前节点
            head = next;      //当前节点变为下一个节点
        }
        return pre;
    }
}

剑指 Offer 35. 复杂链表的复制

题目描述

题目链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

JZ35 复杂链表的复制

方法一：哈希法

/*
// 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 null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node curr = head;
        while(curr != null){ //建立原节点与新节点之间的映射，全部节点入哈希
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        curr = head;
        while(curr != null){ //再次遍历链表，确定新节点的next和random
            Node node = map.get(curr);
            if(curr.next != null){
                node.next = map.get(curr.next);
            }
            if(curr.random != null){
                node.random = map.get(curr.random);
            }
            curr = curr.next;
        }
        return map.get(head);
    }
}

方法二：复制+拆分

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null){
            return null;
        }
        RandomListNode currNode = pHead;
        //1、遍历链表，复制节点，将其插到原对应节点的后面
        while(currNode != null){
            RandomListNode cloneNode = new RandomListNode(currNode.label); //复制的节点
            RandomListNode nextNode = currNode.next; //当前节点的下一个节点
            currNode.next = cloneNode; //当前节点指向复制节点
            cloneNode.next = nextNode; //复制节点指向当前节点的下一个节点
            currNode = nextNode; //当前节点变为下一个节点
        }
        //2、再次遍历链表，复制原节点的random指针给新节点
        currNode = pHead;
        while(currNode != null){
            //当前节点的next即为新节点，当前节点的random的next即为新节点的random
            currNode.next.random = currNode.random == null ? null : currNode.random.next;
            currNode = currNode.next.next; //需要跳到下一个原节点
        }
        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currNode = pHead;
        RandomListNode cloneHead = pHead.next; //新头节点
        RandomListNode cloneNode = cloneHead;
        while(currNode != null){
            currNode.next = cloneNode.next; //新节点的next为原节点之前的next，连接回来
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next; //连接新节点
            currNode = currNode.next;
            cloneNode = cloneNode.next;
        }
        return cloneHead;
    }
}