LintCode 35: Reverse Linked List

题目描述

翻转一个链表。

样例

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

Thu Sep 21 2017

思路

本题的思路很多，今天把之前的方法改进了一下，使用两个指针就可以达到目的了（实际上也用了三个指针，但之前的方法太繁琐了）。

翻转链表的本质是将原本的“箭头”反转，这个操作在只有两个元素的时候很好实现，就一条赋值语句即可。而到了多个元素的时候，只需多考虑一下怎么暂存指针地址，避免链表“断掉”后找不到节点的情况就行了。

代码

// 反转链表class Solution {public:    /**     * @param head: The first node of linked list.     * @return: The new head of reversed linked list.     */    ListNode* reverse(ListNode* head)    {        ListNode* pNewHead;        if (head == NULL || head->next == NULL) return head;        ListNode *p1 = head, *p2 = head->next;        while (p2 != NULL)        {            ListNode* p3 = p2->next;            p2->next = p1;            p1 = p2;            p2 = p3;        }        pNewHead = p1;        head->next = NULL;        return pNewHead;    }};

Mon Mar 6 2017

思路

这道题的方法就很多了，我这里第一想到的就是用三个指针来实现，可能我以前这么实现过吧。

不过这个方法并不是最优的方法，还可以用两个指针，或者递归实现，这些坑以后再补吧。

代码

// 反转链表class Solution {public:    /**     * @param head: The first node of linked list.     * @return: The new head of reversed linked list.     */    ListNode *reverse(ListNode *head) {        ListNode* ans;        if (head == NULL || head->next == NULL) return head;        else if (head->next->next == NULL)        {            head->next->next = head;            ans = head->next;            head->next = NULL;            return ans;        }        ListNode *p1 = head, *p2, *p3;        while(1)        {            p2 = p1->next;            p1 =         }    }    ListNode *reverse(ListNode *head) {        ListNode* ans;        if (head == NULL || head->next == NULL) return head;        else if (head->next->next == NULL)        {            head->next->next = head;            ans = head->next;            head->next = NULL;            return ans;        }        ListNode* p1 = head, *p2 = NULL, *p3 = NULL;        while(1)        {            if (p1 != NULL && p1->next != NULL && p1->next->next != NULL)            {                p2 = p1->next;                p1->next = p3;                p3 = p2->next;                p2->next = p1;                p1 = p3->next;                p3->next = p2;                continue;            }            else if (p1 != NULL && p1->next != NULL && p1->next->next == NULL)            {                ans = p1->next;                ans->next = p1;                p1->next = p3;            }            else if (p1 != NULL && p1->next == NULL)            {                ans = p1;                ans->next = p3;            }            else            {                ans = p3;            }            break;        }        head->next = NULL;        return ans;    }};