Reverse Linked List
Reverse a linked list. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL,
return 5->4->3->2->1->NULL.
Method:
reverse nodes one by one
Solution:
Time: O(n)
Space: O(1)
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode A) {
// 1->2->3->4->5->NULL
//null<-1->2->3->4->5->NULL
//null<-1<-2->3->4->5->NULL
ListNode curr = A;
ListNode prev = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Solution2:
public ListNode reverseList(ListNode A) {
// 1->2->3->4->5->NULL
// 1->2->3->4<-5
// 1->2<-3<-4<-5
if (A == null || A.next == null) return A;
ListNode newHead = reverseList(A.next); // 5
ListNode curr = A; // 4
ListNode next = curr.next; //5
next.next = curr;
curr.next = null;
return newHead;
}