链表逆序

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.双指针迭代法

已知链表头结点指针 head，将链表逆序。（不可以申请额外的空间）

给出链表的节点：

struct ListNode {
	int val;
    ListNode *next;
    // 构造函数
    ListNode(int x) : val(x), next(NULL) {}
};

C++解法 1：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *new_head = NULL;
        while(head){
        	ListNode *next = head->next;
        	head->next = new_head;
        	new_head = head;
        	head = next;
        }
        return new_head;
    }
};

首先保存头结点的下一个节点 next，

然后将旧链表的头节点指向新链表的头结点，

然后将新链表的头节点指向旧链表的头节点（因为旧链表的头节点此时已经成为了新链表的新的头结点）

最后将头结点指向 next（向后移动）

Python3 实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        new = None
        while head is not None:
            nextEl = head.next
            head.next = new
            new = head
            head = nextEl
        return new

2.递归

此方法的思想类似上面的思想，只不过需要放置环路存在。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        start = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return start