Reverse a singly linked list.
GeeksforGeeks
ProgramCreek
YouTube
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
A linked list can be reversed either iteratively or recursively. Could you implement both?
Last updated
Was this helpful?
Was this helpful?
// 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;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
return prev;
}
}/**
* Time complexity :
* Space complexity :
*/
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;
}
}