LeetCode 206. Reverse Linked List(反转链表)
题目描述
Reverse a singly linked list.
解法一
思路
就是经典的头插法了。
def reverseList(head):
if head is None:
return head
new_head = head
while head.next is not None:
current = head.next
head.next = head.next.next
current.next = new_head
new_head = current
return new_head
一图胜千言:
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
new_head = head
while head.next is not None:
current = head.next
head.next = head.next.next
current.next = new_head
new_head = current
return new_head
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode newHead = head;
while (head.next != null) {
ListNode current = head.next;
head.next = head.next.next;
current.next = newHead;
newHead = current;
}
return newHead;
}
}
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseList(ListNode *head) {
if (head == nullptr) {
return head;
}
ListNode *newHead = head;
while (head->next != nullptr) {
ListNode *current = head->next;
head->next = head->next->next;
current->next = newHead;
newHead = current;
}
return newHead;
}
};