剑指offer-链表

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

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

class Solution {
    private int[] res;
    private int length;
    private int index = 0;
    public int[] reversePrint(ListNode head) {
        traverse(head);
        return res;
    }
    private void traverse(ListNode head){
        if(head == null){
            res = new int[length]; 
            return;
        }
        length++;
        traverse(head.next);
        res[index++]=head.val;
    }
}

剑指 Offer 24. 反转链表

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

class Solution {
    //输出反转链表
    //先画图,后编码
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){return head;}
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

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

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

这道题本质上是一个模拟题,要做的就是实现链表的拷贝,难点分析:

首先假设,如果不需要实现random指针的复制,需要怎么用?就是按照普通的做法,根据head来构造一个链表,其伪代码如下:

ListNode copyList(ListNode head){
    ListNode dummmy = new ListNode(-1);
    ListNode cur = head;
    ListNode pre = dummy;
    while(cur!=null){
        ListNode node = new ListNode(cur.val);//复制节点
        pre.next = node;//上一个节点的next指针指向当前节点,把它们连起来
        cur = cur.next;//然后遍历下一个节点
        pre = node;//上一个节点迭代为当前节点,准备下一次复制
    }
    return dummy.next;
}

/*
// 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) {
        //1.提前曝光,先进行普通的复制,把所有的节点都弄出来
        Map<Node,Node> map = new HashMap<>();
        Node dummy = new Node(-1);
        Node pre = dummy;
        Node cur = head;
        while(cur!=null){
            //复制节点
            Node node = new Node(cur.val);
            //连接节点
            pre.next = node;
            //保存节点之间的关系
            map.put(cur,node);
            //迭代节点
            pre = node;
            cur = cur.next;
        }
        //2.生成随机指针
        cur = head;
        while(cur != null){
            if(cur.random == null){
                map.get(cur).random = null;
            }
            //否则的话就是有指向的
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return dummy.next;
    }
}