题目描述

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

一图胜千言：
Reverse Linked List

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;
    }
};