本文共 1347 字，大约阅读时间需要 4 分钟。

题目：反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000

解题：

方法一：双指针

• 我们可以申请两个指针，第一个指针叫 new_next，最初是指向 old_next 的;
• 第二个指针 old_next 指向 head，然后不断遍历 old_next;
• 每次迭代到 old_next，都将 old_next 的 next 指向 new_next，然后 new_next 和 old_next 前进一位;
• 都迭代完了(old_next 变成 null 了)，new_next 就是最后一个节点了。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* reverseList(ListNode* head) {        if (!head || !head->next) return head;        ListNode* new_next = NULL,*old_next = head;        while(old_next) {            ListNode* tmp = old_next->next;            old_next->next = new_next;            new_next = old_next;            old_next = tmp;        }        return new_next;    }};

方法二：递归

递归的两个条件：

• 终止条件是当前节点或者下一个节点==null
• 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句

        head.next.next = head

class Solution {public:    ListNode* reverseList(ListNode* head) {        if (!head || !head->next) return head;//递归终止条件是当前为空，或者下一个节点为空        ListNode* cur = reverseList(head->next);        //这里的cur就是最后一个节点		//如果链表是 1->2->3->4->5，那么此时的cur就是5		//而head是4，head的下一个是5，下下一个是空		//所以head.next.next 就是5->4        head->next->next = head;          head->next = NULL;          return cur;    }};

转载地址：http://wbgen.baihongyu.com/