题目描述
反转一个单链表。
示例:
1 2
| 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
|
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
思路
方案1
采用迭代方法,及循环迭代。用一个变量存储上一节点对象,一个变量存储当前节点对象,一个对象存储下一节点对象。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while(curr!=null){ ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }
|
方案2
采用递归,先递归找到原链表尾巴作为头节点,再依次反转链表。
head.next.next = head;
head.next = null;
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; } }
|
题目链接