剑指 Offer 06. 从尾到头打印链表
上面这道题本身不难,利用栈就可以了。
但是上次小米面试的时候,面试官让我反转一个链表,觉得比这道Offer 06 稍微难一丢丢。赋值顺序、返回的新头节点还是需要思考一下的。
直接用的Offer 06 的数据结构。
【不得不感叹,博客园的代码插入是真难用,复制粘贴格式都要变】
class Solution { public static void main(String[] args) { Solution o = new Solution(); int[] arr = {1,2,3,4}; ListNode head1 = o.create(arr); System.out.println("链表:"); o.print(head1); System.out.println(); ListNode head2 = o.reverse(head1); System.out.println("链表反转后:"); o.print(head2); } //链表反转 public ListNode reverse(ListNode head) { ListNode prev = null; ListNode curr = head; ListNode next = head; while(next != null){ next = curr.next; //这个必须放前面,如果放后面,curr.next就已经被更改为prev了,就丢掉了。 curr.next = prev; prev = curr; curr = next; } //最后一个curr是null,prev才是组后一个元素的地址,也就是新链表的头结点。 return prev; } //根据数组创建链表 public ListNode create(int[] arr){ ListNode head = new ListNode(arr[0]); ListNode curr = head; for(int i = 1;i<arr.length;i++){ ListNode tmp = new ListNode(arr[i]); curr.next = tmp; tmp.next = null; curr = tmp; } return head; } //给定链表头节点,遍历输出链表 public void print(ListNode head){ ListNode curr = head; while(curr != null){ System.out.print(curr.val+" "); curr = curr.next; } } } //链表定义 class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }