15.反转链表.md

15.反转链表

题目描述

• 输入一个链表，反转链表后，输出新链表的表头。

解题思路

• 思路一，一路向下，两个指针，依次遍历结点，先保存下一个结点地址，然后将当前结点的指针反转。很简单，看代码就懂了，但是一定要注意避免出现断链（即忘了先保存下一个结点地址）和环路（即忘记将第一个结点的next改为NULL了）。

• 思路二，递归，很简单，但很巧妙，看代码就懂了。类似于先把所有结点依次入栈，保存最后一个结点的地址为新链表的头结点，然后依次让每个结点出栈，反转指针，将新链表的头结点逐层上传，最后返回出去。

代码

• 方法一，迭代，一路向下

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* p1 = pHead;
        ListNode* p2 = NULL;
        while(p1){
            ListNode* temp = p1->next;
            p1->next = p2;
            p2 = p1;
            p1 = temp;
        }
        return p2;
    }
};

• 方法二，递归

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL || pHead->next==NULL) return pHead;
        
        ListNode* NewListHead = ReverseList(pHead->next);
        
        pHead->next->next = pHead;
        pHead->next = NULL;
        
        return NewListHead;
    }
};