35 翻转链表

原题网址：http://www.lintcode.com/zh-cn/problem/reverse-linked-list/#

翻转一个链表

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

挑战 

在原地一次翻转完成

标签 

微软 亚马逊 Bloomberg 脸书 链表 优步 苹果Yelp 雅虎 Adobe Zenefits 推特 Snapchat

 

思路：new一个尾节点，其数值等于head数值，遍历head，从后向前挂载节点。

 

/**
 * Definition of singly-linked-list:
 *
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        // write your code here
        if (head==NULL)
     {
         return head;
     }

     ListNode *tail=new ListNode(head->val);
     
     while(head->next!=NULL)
     {
         head=head->next;
         ListNode *newNode=new ListNode(head->val);
         newNode->next=tail;
         tail=newNode;
     }

     return tail;
    }
};

挑战，原地一次翻转。

刚开始抓破头皮想不到，后来上网搜了下参照了别人的想法码了出来，链接：https://www.cnblogs.com/lelelelele/p/6109949.html

具体思路：

设置三根指针分别指向翻转后的当前节点，前置节点，与后继节点。

当前节点cur不为空时，pre=cur->next（保存下次要处理的节点）。

接下来curNode->next=nextNode与nextNode=curNode，当前节点与原链表断开，其后继节点为上次循环的cur（画个图就明白了，或者看上面链接）。

然后是curNode=preNode，这句的意思是移动到原链表下个节点，判断是否进入下次循环。

循环结束时，cur与pre都为NULL，要返回上次的cur（原链表的尾节点），即nextNode。

 

PS：其实普通单链表的挂载只需要知道当前节点和后继节点就可以了，本题设置pre是为了移动遍历原链表。

 

/**
 * Definition of singly-linked-list:
 *
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        // write your code here
         if (head==NULL)
     {
         return head;
     }

     //挑战：原地翻转;
    ListNode *curNode=head;
    ListNode *preNode=NULL;
    ListNode *nextNode=NULL;
    while(curNode!=NULL)
    {
        preNode=curNode->next;
        curNode->next=nextNode;
        nextNode=curNode;
        curNode=preNode;    
    }
    
    return nextNode;
    }
};