Linked list (simple)

The finger of the sword Offer 06. Print linked list from end to end
The finger of the sword Offer 24. Reverse a linked list
The finger of the sword Offer 35. Replication of complex linked list

The finger of the sword Offer 06. Print linked list from end to end - Power button （LeetCode）

Definition of a single linked list ：

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

One ： Stack method

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        Stack<ListNode> stack=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
    
            stack.push(cur);
            cur=cur.next;
        }
        int[] arr=new int[stack.size()];
        for(int i=0;i<arr.length;i++){
    
            arr[i]=stack.pop().val;
        }
        return arr;
    }
}
/**  Complexity analysis ：  Time complexity  O(N)  Spatial complexity  O(N) */

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
    
            stack.addLast(head.val);//addLast() Method is used in LinkedList Insert a specific element at the end of 
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();//removeLast() Method is used to get from LinkedList Delete the last element in 
    return res;
    }
}

/**  Complexity analysis ：  Time complexity  O(N)： Stack in and stack out are used together O(N) Time .  Spatial complexity  O(N)： Auxiliary stack stack And an array res Use together O(N) Extra space  */

Two ： Recursive method

Algorithm flow ：

• Recurrence stage ： Every time I pass in head.next , With head == null（ That is, walk through the tail node of the linked list ） Is a recursive termination condition , Go straight back to .
• Backtracking phase ： When you go back layer by layer , Add the current node value to the list , namely tmp.add(head.val).
  Final , Will list tmp Convert to array res , And return .

Complexity analysis

• Time complexity O(N)： Traversing the linked list , recursive N Time .
• Spatial complexity O(N)： System recursion needs to use O(N) Stack space of .

class Solution {
    
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
    
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head) {
    
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

3、 ... and ：

class Solution {
    
    //  Execution time  : 0 ms,  In all  Java  Defeated in submission  100.00%  Users of 
    //  Memory consumption  : 39.8 MB,  In all  Java  Defeated in submission  100.00%  Users of 
    //  No stack , Do not use recursion , Anyway, it is also scanned twice , Why allocate extra space ？
    public static int[] reversePrint(ListNode head) {
    
        ListNode node = head;
        int count = 0;
        while (node != null) {
    
            ++count;
            node = node.next;
        }
        int[] nums = new int[count];
        node = head;
        for (int i = count - 1; i >= 0; --i) {
    
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}

The finger of the sword Offer 24. Reverse a linked list - Power button （LeetCode）

One ： iteration

/** * 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 pre=null;
        ListNode cur=head;
        ListNode tmp=null;
        while(cur!=null){
    
            tmp=cur.next;//  Staging successor nodes  cur.next
            cur.next=pre;//  modify  next  Reference point 
            pre=cur;// pre  The staging  cur
            cur=tmp;// cur  Visit the next node 
        }
        return pre;
    }
}

Two ： recursive

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        return recur(head, null);    //  Call recursion and return 
    }
    
    private ListNode recur(ListNode cur, ListNode pre) {
    
        if (cur == null){
    
            return pre; //  Termination conditions 
        } 
        ListNode res = recur(cur.next, cur);  //  Recursive successor node 
        cur.next = pre;              //  Modify the node reference to 
        return res;                  //  Returns the header node of the inverted linked list 
    }
}

The finger of the sword Offer 35. Replication of complex linked list - Power button （LeetCode）

One ： Hashtable

/* // 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) {
    
        Map<Node, Node> m = new HashMap<>();
        Node p = head;
        while(head != null) {
    
            Node t = new Node(head.val);
            m.put(head, t);
            head = head.next;
        }
        head = p;
        // According to the original linked list , Look up the hash table and connect the new linked list 
        while(head != null) {
    
            Node n = head.next; // The next node of the original node 
            Node r = head.random;// Original node random node 
            // New nodes next Point to the next new node 
            m.get(head).next = m.get(n);
            // Set the new node's random The node points to 
            m.get(head).random = m.get(r);
            head = head.next;
        }
        return m.get(p);
    }
}

class Solution {
    
    public Node copyRandomList(Node head) {
    
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // Copy each node , And establish  “ Original node  ->  New node ”  Of  Map  mapping 
        while(cur != null) {
    
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // To build a new linked list  next  and  random  Point to 
        while(cur != null) {
    
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // Return the head node of the new linked list 
        return map.get(head);
    }
}