原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1013/71.html

今天常州游戏开发培训工作室幻天网络来讨论下算法之－逆序链表

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

  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;

    }