Easy

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

 

题目大意：将链表反转。尝试使用递归和迭代两种方法进行解答。

 

方法：

方法一：迭代法

基本思路就是将链表循环一圈，操作方法就是定义两个新的ListNode，让其中一个指节点temp用于标记没有进行反转的链表部分的开头。这里我们需要将head赋值为temp的next的next，便于循环运算。另一个节点cur赋值为head。利用cur寻找链表的末尾，将末尾的那个元素插入到temp后边，然后将temp后移一位，再次进行这样的操作。直至head的next为空为止，这时就表明原本位于第一位的节点移动到了链表的末尾。为了能返回排列后的链表，我们还需要一个静止的ListNode，定义为dummy，让他始终指向链表的头结点，链表完成反转后，程序返回dummy的next即可。具体代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)return NULL;
        ListNode *temp=new ListNode(-1),*dummy = new ListNode(-1);
        dummy->next = head;
        temp->next = dummy;
        while (head->next) {
            ListNode *cur = head;
            temp = temp->next;
            while (cur->next && cur->next->next) {
                cur = cur->next;
            }
            cur->next->next = temp->next;
            temp->next = cur->next;
            cur->next = NULL;
        }
        return dummy->next;
    }
};

 

方法二：递归法

递归的方法我也使用了和上述相似的思路，只不过不再使用temp来标记需要反转的链表部分的开头，而是直接对需要反转的部分调用反转函数。具体代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)return head;
        ListNode *dummy = new ListNode(-1),*cur=head;
        dummy->next = head;
        while (cur->next && cur->next->next) {
            cur = cur->next;
        }
        cur->next->next = dummy->next;
        dummy->next = cur->next;
        cur->next = NULL;
        dummy->next->next=reverseList(head);
        return dummy->next;
    }
};