反转链表和反转链表2

 LeetCode 206. Reverse Linked List

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?

思路：

C++代码：

ListNode* reverseList(ListNode* head)
{
    ListNode* prev = NULL;
    while (head)
    {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

 

 

LeetCode 92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

思路：

 

C++代码：

ListNode* reverseBetween(ListNode* head, int m, int n)
{
    ListNode dummy = ListNode(-1), * prev = &dummy, * cur;
    dummy.next = head;
    for (int i = 0; i < m - 1; i++)
    {
        prev = prev->next;
    }
    cur = prev->next;
    for (int i = 0; i < n - m; i++)
    {
        ListNode* tmp = prev->next;
        prev->next = cur->next;
        cur->next = cur->next->next;
        prev->next->next = tmp;
    }
    return dummy.next;
}

 注：ListNode dummy = ListNode(-1)而不是ListNode dummy = new ListNode(-1); 可以防止内存泄露，省去手动释放内存的过程。