206 - Reverse Linked List
Written on October 21, 2015
Tweet
Reverse a singly linked list.
public class Solution {
/**
* @param head: The head of linked list.
* @return: The new head of reversed linked list.
*/
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode rev = null;
while (head != null) {
ListNode next = head.next;
head.next = rev;
rev = head;
head = next;
}
return rev;
}
//recursiton
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode rev = reverseList(head.next);
//head.next is the last element in rev, we connect it to the first element, and clear the first element.
head.next.next = head;
head.next = null;
return rev;
}
}
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return
rev = None
while head:
next_node = head.next
head.next = rev
rev = head
head = next_node
return rev
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* dummy = NULL;
while (head != NULL) {
ListNode* next1 = head->next;
head->next = dummy;
dummy = head;
head = next1;
}
return dummy;
}
};