[LeetCode] 92. 反转链表 II

[Animenzzzz]

题目描述：

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路：这题自己的写法复杂了。
执行用时 :0 ms, 在所有 C 提交中击败了 100.00% 的用户
内存消耗 :7.3 MB, 在所有 C 提交中击败了 19.81% 的用户
竟然击败100%，可能是因为分了情况的处理。。。
思路：首先遍历一遍找到m，n对应的节点和其前驱节点。然后分情况
1.交换的是最后两个节点（1）只有两个节点（2）多余两个节点 需要处理这个情况是因为我发现current->next->next可能会为空。。
2.要换头结点和不换头结点（唯一的区别就是是否需要新建一个指针指向head）

C解题：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n){
    if(!head) return NULL;
    if(m == n) return head;
    struct ListNode* tmp_head = head;
    struct ListNode* m_node = head;
    struct ListNode* m_pre_node = NULL;
    struct ListNode* n_node = head;
    struct ListNode* n_pre_node = NULL;
    for (int i = 1; i < n; i++)
    {
        if(i <= m-1){
            m_pre_node = m_node;
            m_node = m_node->next;
        }
        n_pre_node = n_node;
        n_node = n_node->next;
    }
    if(m == 1) m_pre_node = NULL;
    struct ListNode* current = m_node;
    struct ListNode* current_next_next = current->next->next;
    //说明交换的是最后两个节点
    if(!current_next_next){
        //说明链表只有两个节点
        if (!m_pre_node)
        {
            n_node->next = m_node;
            m_node->next = NULL;
            return n_node;
        }else{
            m_pre_node->next = n_node;
            n_node->next = m_node;
            m_node->next = NULL;
            return head;
        }
    }
    tmp_head = head;
    //要换头结点 
    if(!m_pre_node){
        struct ListNode* dummy_head = (struct ListNode*)malloc(sizeof(struct ListNode));
        dummy_head->next = head;
        m_pre_node = dummy_head;
        for (int i = 1; i <= n-m; i++)
        {
            current->next->next = m_pre_node->next;
            m_pre_node->next = current->next;
            current->next = current_next_next;
            current_next_next = current_next_next ? current_next_next->next:NULL;
        }
        return dummy_head->next;
    }
    for (int i = 1; i <= n-m; i++)
    {
        current->next->next = m_pre_node->next;
        m_pre_node->next = current->next;
        current->next = current_next_next;
        current_next_next = current_next_next ? current_next_next->next:NULL;
    }
    return head;
}