lintcode 翻转链表

描述

翻转一个链表

样例

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

挑战

在原地一次翻转完成

思路

在原地反转，那么就是一边迭代一边跟新每个节点的next指针，把当前节点cur 指向cur->next->next 他的下一个节点指向head，最后跟新一下节点的信息。返回head。因为涉及到了4个 head cur cur->next cur->next->next 所以退出循环的条件是cur->next == null

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

        while (cur->next){
            temp = cur->next;
            cur ->next = cur->next->next;
            temp->next = head;
            head = temp;
        }
        return head;
    }
};

更新 2019/2/21

在做翻转链表2的时候发现自己翻转链表的算法写的太过复杂，于是进行了简化，主要是第一次写的算法逻辑不是很清晰。第二次的简单多了。

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

-------------end of filethanks for reading-------------