首页 🍒LeetCode,🐶算法

题目

ll2peGxYe0.png

思路

一:两次遍历:
转换过程类似于头插法创建链表。

交换相邻的i,j节点(p为i前面的节点):
j = i->next;
i->next = p;
p = i;
i = j;
(代码非常粗糙,慎重观看)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *listleft, *listright, *node, *temp, *pre = nullptr, *ltemp = nullptr, *rtemp = nullptr;
        int m = 1;
        node = head;
        listleft = head;
        while (m < right) {
            if (m == left - 1) {
                listleft = node->next;
                ltemp = node;
            }
            m++;
            node = node->next;
        }
        listright = node;
        rtemp = node->next;
        node = listleft;
        while (node != rtemp) {
            temp = node->next;
            node->next = pre;
            pre = node;
            node = temp;
        }
        if (left != 1) ltemp->next = listright;
        else head = listright;
        listleft->next = rtemp;
        return head;
    }
};

二:一次遍历:
遍历找到left,然后开始反转:
原本的left节点指向新节点的下一个,将新的节点插入到left位置。直到遇到right,转换结束

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right)
    {
        if (right == 1) return head;
        ListNode *temp = nullptr, *node = nullptr;
        ListNode *pre = (ListNode *)malloc(sizeof(ListNode));
        int m = 1;
        node = head;
        if (left != 1)
        {
            while (m < left - 1)
            {
                m++;
                node = node->next;
            }
            pre = node;
            m++;
            node = node->next;
        }
        else {
            pre->next = head;
        }
        while (m++ < right)
        {
            temp = node->next;
            node->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        if (left == 1)
            head = temp;
        return head;
    }
};



文章评论