题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

样例

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

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

算法

(链表操作，迭代) $O(n)$

翻转即将所有节点的next指针指向前驱节点。
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。

空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是 $O(1)$。
时间复杂度分析：只遍历一次链表，时间复杂度是 $O(n)$。

参考文献

yxc大神的题解

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) {
        ListNode*prev=NULL;
        ListNode*cur=head;
        while(cur!=NULL){
            ListNode*next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};

C 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode*prev=NULL;
    struct ListNode*cur=head;
    while(cur!=NULL){
        struct ListNode*next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
}

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 prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
}

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
        """
        prev=None
        cur=head
        while cur!=None:
            next=cur.next
            cur.next=prev
            prev=cur
            cur=next
        return prev

Javascript 代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    var prev=null;
    var cur=head;
    while(cur!=null){
        var next=cur.next;
        cur.next=prev;
        prev=cur;
        cur=next;
    }
    return prev;
};

Python3代码

# 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
        """
        prev=None
        cur=head
        while cur!=None:
            next=cur.next
            cur.next=prev
            prev=cur
            cur=next
        return prev

Go 代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev*ListNode
    cur:=head
    for cur!=nil{
        next:=cur.Next
        cur.Next=prev
        prev=cur
        cur=next
    }
    return prev
}