鏈錶（簡單）

劍指 Offer 06. 從尾到頭打印鏈錶
劍指 Offer 24. 反轉鏈錶
劍指 Offer 35. 複雜鏈錶的複制

劍指 Offer 06. 從尾到頭打印鏈錶 - 力扣（LeetCode）

單鏈錶的定義：

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

一：棧方法

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;
    }
}
/** 複雜度分析： 時間複雜度 O(N) 空間複雜度 O(N) */

class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
    
            stack.addLast(head.val);//addLast()方法用於在LinkedList的末尾插入特定元素
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();//removeLast()方法用於從LinkedList中删除最後一個元素
    return res;
    }
}

/** 複雜度分析： 時間複雜度 O(N)：入棧和出棧共使用O(N)時間。 空間複雜度 O(N)：輔助棧stack和數組res共使用O(N)的額外空間 */

二：遞歸法

算法流程：

• 遞推階段： 每次傳入 head.next ，以 head == null（即走過鏈錶尾部節點）為遞歸終止條件，此時直接返回。
• 回溯階段： 層層回溯時，將當前節點值加入列錶，即tmp.add(head.val)。
  最終，將列錶 tmp 轉化為數組 res ，並返回即可。

複雜度分析

• 時間複雜度 O(N)： 遍曆鏈錶，遞歸 N 次。
• 空間複雜度 O(N)：系統遞歸需要使用 O(N) 的棧空間。

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);
    }
}

三：

class Solution {
    
    // 執行用時 : 0 ms, 在所有 Java 提交中擊敗了 100.00% 的用戶
    // 內存消耗 : 39.8 MB, 在所有 Java 提交中擊敗了 100.00% 的用戶
    // 不使用棧，不使用遞歸，反正怎麼樣也是掃描兩趟，為什麼要額外分配空間呢？
    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;
    }
}

劍指 Offer 24. 反轉鏈錶 - 力扣（LeetCode）

一：迭代

/** * 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;// 暫存後繼節點 cur.next
            cur.next=pre;// 修改 next 引用指向
            pre=cur;// pre 暫存 cur
            cur=tmp;// cur 訪問下一節點
        }
        return pre;
    }
}

二：遞歸

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        return recur(head, null);    // 調用遞歸並返回
    }
    
    private ListNode recur(ListNode cur, ListNode pre) {
    
        if (cur == null){
    
            return pre; // 終止條件
        } 
        ListNode res = recur(cur.next, cur);  // 遞歸後繼節點
        cur.next = pre;              // 修改節點引用指向
        return res;                  // 返回反轉鏈錶的頭節點
    }
}

劍指 Offer 35. 複雜鏈錶的複制 - 力扣（LeetCode）

一：哈希錶

/* // 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;
        //根據原鏈錶，查找哈希錶將新鏈錶連起來
        while(head != null) {
    
            Node n = head.next; //原始節點的下一個節點
            Node r = head.random;//原始節點隨機節點
            //新節點的next指向下一個新節點
            m.get(head).next = m.get(n);
            //設置新節點的random結點指向
            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<>();
        //複制各節點，並建立 “原節點 -> 新節點” 的 Map 映射
        while(cur != null) {
    
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        //構建新鏈錶的 next 和 random 指向
        while(cur != null) {
    
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回新鏈錶的頭節點
        return map.get(head);
    }
}