反转链表(迭代和递归)

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

链表头结点head

迭代(双指针)

• 定义两个ListNode指针，pre指向现在的节点，cur指向前一个节点

• 每次让pre的next指向cur

• 反转后，pre和cur往前循环

• 循环至链表末尾NULL

  

struct ListNode{
    int val;
    ListNode *next;
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* tempnext = pre->next;
            pre->next = cur;
            cur = pre;
            pre = tempnext;
        }
        return cur;
    }
};

递归

• 递归到链表最后一个结点，该结点就是反转后的头结点，作为返回对象p
• 每次返回过程中，让当前结点的下一个结点的next指向当前结点
• 同时让当前结点的next指向null(指针地址为空，不是下一个结点删除为空)
• 实现反转
  

struct ListNode{
    int val;
    ListNode *next;
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        ListNode *p=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return p;
    }
};

注意：

• 链表head->next储存的是下一个结点的地址，head->next为空不是删除那个结点。