[剑指offer] 链表篇

JZ6 从尾到头打印链表

  1 /* 从尾到头递归 */
  2 public class JZ6_1
  3 {
  4     private static ArrayList<Integer> res = new ArrayList<>();
  5 
  6     public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
  7     {
  8         if (listNode != null)
  9         {
 10             printListFromTailToHead(listNode.next);
 11             res.add(listNode.val);
 12         }
 13         return res;
 14     }
 15 }
 16 
 17 /* ArrayList.add(int index, E element) */
 18 public class JZ6_2
 19 {
 20     public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
 21     {
 22         ArrayList<Integer> res = new ArrayList<>();
 23         while (listNode != null)
 24         {
 25             res.add(0, listNode.val);
 26             listNode = listNode.next;
 27         }
 28         return res;
 29     }
 30 }
 31 
 32 /* 栈 */
 33 public class JZ6_3
 34 {
 35     public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
 36     {
 37         ArrayList<Integer> res = new ArrayList<>();
 38         Stack<Integer> temp = new Stack<>();
 39         while (listNode != null)
 40         {
 41             temp.add(listNode.val);
 42             listNode = listNode.next;
 43         }
 44         while (!temp.isEmpty())
 45         {
 46             res.add(temp.pop());
 47         }
 48         return res;
 49     }
 50 }
 51 
 52 /* 原地反转链表 */
 53 public class JZ6_4
 54 {
 55     public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
 56     {
 57         ListNode pre = null, cur = listNode, temp = null;
 58         ArrayList<Integer> res = new ArrayList<>();
 59         while (cur != null)
 60         {
 61             temp = cur.next;
 62             cur.next = pre;
 63             pre = cur;
 64             cur = temp;
 65         }
 66         while (pre != null)
 67         {
 68             res.add(pre.val);
 69             pre = pre.next;
 70         }
 71         return res;
 72     }
 73 }
 74 
 75 /* 递归反转链表 */
 76 public class JZ6_5
 77 {
 78     public static ArrayList<Integer> printListFromTailToHead(ListNode listNode)
 79     {
 80         ArrayList<Integer> res = new ArrayList<>();
 81 
 82         ListNode reverseList = reverse(listNode);
 83         while (reverseList != null)
 84         {
 85             res.add(reverseList.val);
 86             reverseList = reverseList.next;
 87         }
 88         return res;
 89     }
 90 
 91     public static ListNode reverse(ListNode node)
 92     {
 93         if (node == null || node.next == null) return node;
 94         ListNode fir = node, sec = node.next;
 95         fir.next = null;
 96         ListNode temp = sec;
 97         ListNode reverse = reverse(sec);
 98         temp.next = fir;
 99         return reverse;
100     }
101 }

 JZ24 反转链表

 1 /* 从尾到头递归 */
 2 public class JZ24_1
 3 {
 4     public static ListNode res, tail;
 5 
 6     public static ListNode ReverseList(ListNode listNode)
 7     {
 8         if (listNode != null)
 9         {
10             ReverseList(listNode.next);
11             if (res == null)
12                 res = tail = listNode;
13             else
14             {
15                 tail.next = listNode;
16                 tail = tail.next;
17                 tail.next = null;
18             }
19         }
20         return res;
21     }
22 }
23 
24 /* 栈 */
25 public class JZ24_2
26 {
27     public static ListNode ReverseList(ListNode listNode)
28     {
29         ListNode head = new ListNode(-1), tail = head;
30         Stack<Integer> temp = new Stack<>();
31         while (listNode != null)
32         {
33             temp.add(listNode.val);
34             listNode = listNode.next;
35         }
36         while (!temp.isEmpty())
37         {
38             tail.next = new ListNode(temp.pop());
39             tail = tail.next;
40         }
41         return head.next;
42     }
43 }
44 
45 /* 原地反转链表 */
46 public class JZ24_3
47 {
48     public static ListNode ReverseList(ListNode listNode)
49     {
50         ListNode pre = null, cur = listNode, temp = null;
51         while (cur != null)
52         {
53             temp = cur.next;
54             cur.next = pre;
55             pre = cur;
56             cur = temp;
57         }
58         return pre;
59     }
60 }
61 
62 /* 递归反转链表 */
63 public class JZ24_4
64 {
65     public static ListNode ReverseList(ListNode listNode)
66     {
67         if (listNode == null || listNode.next == null) return listNode;
68         ListNode fir = listNode, sec = listNode.next;
69         fir.next = null;
70         ListNode temp = sec;
71         ListNode reverse = ReverseList(sec);
72         temp.next = fir;
73         return reverse;
74     }
75 }