LeetCode—— 反转链表

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

一、CPP

解题思路:链表逆序首先想到的方法就是头插法，下面实现代码中，新建了两个节点，进行就地逆置。一个用作新链表的头节点，一个用作原链表的遍历。
时间复杂度:O(n)。

/**
 * 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) {

        ListNode* new_head = new ListNode(-1);
        ListNode* p = head;

        while(head){
            p = p->next;
            //头插法
            head->next = new_head->next;
            new_head->next = head;

            head = p;

        }

        return new_head->next;
    }
};

二、Java实现（同一）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode new_head = new ListNode(-1);

        ListNode p = head;

        while(head!=null){

            p = head.next;

            head.next = new_head.next;
            new_head.next = head;

            head = p;
        }

        return new_head.next;
    }
}

三、Python实现（同一）

# Definition for singly-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
        """
        new_head = ListNode(-1)
        p = head

        while head!=None:

            p = head.next

            head.next = new_head.next
            new_head.next = head

            head = p

        return new_head.next

四、各语言及算法时间复杂度

各语言及算法时间复杂度