[thinking]

For the simplest problem, suppose the linked list looks like this:

1-》2-》3-》4

The new list header newhead points to 1, cur points to 2, and disconnects 1 from 2:

1 2-》3-》4

Insert the head node of the back list before the head node of the front list. It takes no extra memory.

[code]

python:
class Solution:
    # returns ListNode
    def ReverseList(self, pHead):
        if not pHead:
            return None
        cur=pHead.next
        newhead=pHead
        pHead.next=None
        while(cur):
            next_=cur.next
            cur.next=newhead
            newhead=cur
            cur=next_
        return newhead
Copy the code
C++:
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL){
            return NULL;
        }
        ListNode* newhead=pHead;
        ListNode* cur=pHead->next;
        newhead->next=NULL;
        ListNode* next_=NULL;
        while(cur! =NULL){ next_=cur->next; cur->next=newhead; newhead=cur; cur=next_; }returnnewhead; }};Copy the code