单线链表逆序

reverse linklist

https://leetcode.com/problems/reverse-linked-list/

一个链表的逆序
Python和Java的实现
去面试碰到这个题,答题的时候没有太多把握,现在写下来看看。

# -*- coding: utf-8 -*-

# https://leetcode.com/problems/reverse-linked-list/

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        next_tmp = None
        prev = None
        curr = head

        while curr != None:
            next_tmp = curr.next
            curr.next = prev
            prev = curr
            curr = next_tmp

        return prev

class Solution2(object):
    def reverseList(self, head):
        if head == None or head.next == None:
            return head

        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

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