链表（简单）

剑指 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; 
    }
}
1
2
3
4
5
6
7
8

一：栈方法

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)
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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)的额外空间
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二：递归法

算法流程：

• 递推阶段： 每次传入 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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

剑指 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二：递归

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;                  // 返回反转链表的头节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

剑指 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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21