反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
1 class Solution206 { 2
3 //迭代
4 public ListNode reverseList(ListNode head) { 5 ListNode dummyHead = new ListNode(0); 6 dummyHead.next = head; 7 ListNode node = head; 8 ListNode newDummyHead = new ListNode(0); 9
10 while (node != null) { 11 dummyHead.next = node.next; 12 node.next = newDummyHead.next; 13 newDummyHead.next = node; 14 node = dummyHead.next; 15 } 16 return newDummyHead.next; 17 } 18
19 //递归
20 public ListNode reverseList_2(ListNode head) { 21 if (head == null || head.next == null) { 22 return head; 23 } 24 ListNode newHead = reverseList_2(head.next); 25 head.next.next = head; 26 head.next = null; 27 return newHead; 28
29 } 30
31 }