al

Reverse Linked List- 链表翻转

Reverse a linked list.

Example
For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge
Reverse it in-place and in one-pass

题解：

联想到同样也可能需要翻转的数组，在数组中由于可以利用下标随机访问，翻转时使用下标即可完成。而在单向链表中，仅仅只知道头节点，而且只能单向往前走，故需另寻出路。分析由1->2->3变为3->2->1的过程，由于是单向链表，故只能由1开始遍历，1和2最开始的位置是1->2，最后变为2->1，故从这里开始寻找突破口，探讨如何交换1和2的节点。

temp = head->next;
head->next = prev;
prev = head;
head = temp;

要点在于维护两个指针变量prev和head. 分析如下图所示：

Reverse Linked List

保存head下一节点
将head所指向的下一节点改为prev
将prev替换为head，波浪式前进
将第一步保存的下一节点替换为head，用于下一次循环

C++

/**
 * http://www.jiuzhang.com/solutions/reverse-linked-list/
 * Definition of ListNode
 *
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        ListNode *prev = NULL;
        while (head) {
            ListNode *temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }
};

源码分析：

题解中基本分析完毕，代码中的prev赋值比较精炼，值得借鉴。

Reference

反转单向链表的四种实现（递归与非递归，C++） | 宁心勉学，慎思笃行

Reverse Linked List II

Question: (36) Reverse Linked List II

Reverse a linked list from position m to n.

Note
Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Example
Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Challenge
Reverse it in-place and in one-pass

题解：

此题在上题的基础上加了位置要求，只翻转指定区域的链表。由于链表头节点不确定，祭出我们的dummy杀器。此题边界条件处理特别tricky，需要特别注意。

由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点
找到第m个节点，使用for循环n-m次，使用上题中的链表翻转方法
处理第m-1个和第n+1个节点
返回dummy->next

C++

/**
 * Definition of singly-linked-list:
 *
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The head of linked list.
     * @param m: The start position need to reverse.
     * @param n: The end position need to reverse.
     * @return: The new head of partial reversed linked list.
     */
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == NULL || m > n) {
            return NULL;
        }

        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *node = dummy;

        for (int i = 1; i != m; ++i) {
            if (node == NULL) {
                return NULL;
            } else {
                node = node->next;
            }
        }

        ListNode *premNode = node;
        ListNode *mNode = node->next;
        ListNode *nNode = mNode, *postnNode = nNode->next;
        for (int i = m; i != n; ++i) {
            if (postnNode == NULL) {
                return NULL;
            }

            ListNode *temp = postnNode->next;
            postnNode->next = nNode;
            nNode = postnNode;
            postnNode = temp;
        }
        premNode->next = nNode;
        mNode->next = postnNode;

        return dummy->next;
    }
};

源码分析：

处理异常
使用dummy辅助节点
找到premNode——m节点之前的一个节点
以nNode和postnNode进行遍历翻转，注意考虑在遍历到n之前postnNode可能为空
连接premNode和nNode，premNode->next = nNode;
连接mNode和postnNode，mNode->next = postnNode;

务必注意node 和node->next的区别！！，node指代节点，而node->next指代节点的下一连接。

al

￼Reverse Linked List- 链表翻转

Reference

Reverse Linked List II

Reverse Linked List- 链表翻转