假设单链表数据结构定义如下：

struct ListNode {      int val;      ListNode *next;      ListNode(int x) : val(x), next(NULL) {}  };

单链表有一个头指针指向第一个结点，最后一个结点指向NULL

 

一、最容易想到的方法，新建一个单链表newNode，每次将原先链表的第一个结点放到newNode后

ListNode* reverseList(ListNode* head) {        ListNode *newNode = new ListNode(0);//新链表头结点        ListNode *tmp;//指向原先链表的第一个结点        newNode->next = head;        ListNode *cur = head;        while(cur && cur->next)        {        tmp = newNode->next;//保存后续结点        newNode->next = cur->next;//将原先链表的第一个结点放到新链表中                                 cur->next = cur->next->next;//从原先链表中摘除这个结点        newNode->next->next = tmp;//恢复新链表中后续结点的指针        }        return newNode;            }

 

二、每次将原第一个结点后的结点放在head后面

ListNode* reverseList(ListNode* head) {       ListNode *tmp = NULL;       ListNode *cur = NULL;       if(!head) return NULL;       cur = head->next;       while(cur)       {              tmp = cur->next;              cur->next  = tmp->next;              tmp->next = head->next;              head->next = tmp;       }          return head;    }

 

三、与第二种方法类似,推荐这种方法

ListNode* reverseList(ListNode* head) {        ListNode *cur = head;        ListNode *tmp, *prev = NULL;        while (cur)        {            tmp = cur->next;            cur->next = prev;            prev = cur;            cur = tmp;        }        return prev;    }