Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
两种解法:递归、迭代
递归法(Recursion):
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode next = head.next; ListNode reverseHead = reverseList(next); next.next = head; head.next = null; return reverseHead; } }
迭代法(iteration)
也叫头插法,每次取原链表中的第一个结点,插到新链表的头部。这样原链表第一个结点就会变成,新链表的最后一个结点。最终返回新链表头结点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode reverse = null; ListNode cur = head; while(cur != null) { ListNode temp = cur; cur = cur.next; temp.next = reverse; reverse = temp; } return reverse; } }