Sword finger offer 06.24.35 Linked list

Topic 1 ： 

The finger of the sword Offer 06. Print linked list from end to end https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

idea ： Put the linked list into the array in reverse order Then return the array

Code ：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode node=head;
        Stack<Integer> st= new Stack<>();
        int cnt=0;
        int i=0;
        if(node==null)
            return new int[0];
        // Count the number of nodes 
        while(node.next!=null){
            node=node.next;
            cnt++;
        }      
        node=head;
        int[] print = new int[cnt+1];
        // Put the linked list into the array in reverse order  
        for(i=cnt;i>=0;i--){
            print[i]=node.val;
            node=node.next;
        }
        return print;
    }
}

result ：

  Topic two ：

The finger of the sword Offer 24. Reverse a linked list https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

idea ：  Create a new header node Reverse a linked list

Code ：

/**
 * 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 node;
        ListNode reverse = new ListNode();
        reverse.next=head;
        if(head==null)
            return null;
        while(head.next!=null){
            node=head.next;
            head.next=node.next;
            node.next=reverse.next;
            reverse.next=node;
        }     
        return reverse.next;
    }
}

result ：

Topic three ：

The finger of the sword Offer 35. Replication of complex linked list https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

idea ： Repeat this node after each node And then the odd position of the node random Field to the next node Finally, split the original linked list and the result linked list

Code ：

/*
// 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;
        // Auxiliary nodes 
        Node curr = head;
        // Repeat each node   Form a new linked list 
        // Traverse each node   So the termination conditions ：curr!=null
        while(curr!=null){
            Node temp=new Node(curr.val);
            temp.next=curr.next;
            curr.next=temp;
            curr=curr.next.next; // or  curr=temp.next;
        }
        // Give duplicate nodes   Fu random Domain value 
        curr=head;
        // Through each ( Singular position ) node   So the termination conditions ：curr!=null
        while(curr!=null){
            // Empty is already empty without assignment 
            if(curr.random!=null)
                curr.next.random=curr.random.next;
            curr=curr.next.next;
        }
        // Split two linked lists of odd and even numbers 
        //ori For the original linked list   because 【 Copy the linked list 】 It is required not to change the original linked list 
        Node ori=head;
        //res Point to the new list ( Result list ) The head of the 
        Node res=head.next;
        curr=head.next;
        
        // Traverse to the last node and stop   So the termination conditions ：curr.next!=null
        while(curr.next!=null){
            ori.next=ori.next.next;
            curr.next=curr.next.next;
            ori=ori.next;
            curr=curr.next;
        }
        // Finally, don't forget to empty the end of the original linked list 
        ori.next=null;
        // Return result list 
        return res;
        
    }
}

  result ：