首页 > 代码库 > Leetcode:Rotate List 链表旋转

Leetcode:Rotate List 链表旋转

2024-07-08 00:17:15   213人阅读

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

 

解题分析：

不同于数组旋转，数组可以随机存取，数组的旋转可以巧妙的 分成两两部分递归旋转

对于链表的旋转，实际上就是把后一部分连续的尾插法插入到新的结果链表中

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        assert(k >= 0);
        if (head == nullptr) return nullptr;
        ListNode* cur = head;
        int listLen = 0;
        while (cur != NULL) {
            ++listLen;
            cur = cur->next;
        }
        k %= listLen;
        
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        
        ListNode* resHead = new ListNode(0);
        ListNode* resCur = resHead;
        
        cur = newHead;
        for (int i = 0; i < listLen - k; ++i) {
            cur = cur->next;
        }
        
        ListNode* resTail = cur;
        for (int i = 0; i < k; ++i) {
            ListNode* nextNode = cur->next;
            ListNode* tmp = nextNode->next;
            resCur->next = nextNode;
            resCur = nextNode;
            cur->next = tmp;
        }
        resCur->next = newHead->next;
        resTail->next = NULL;
        return resHead->next;
    }
};

需要注意以下几点：

1. K的取值，因为k值可以很大，我们可以将k对链表长度取余，因为每旋转一个链表长度相当于复原了

2. 虚拟前置结点指向链表的第一个结点，因为头节点也可能被修改，而头节点的修改操作和其余结点的操作不统一，因此采用一个虚拟的前置结点

3. 我们从虚拟的前置结点newHead前进listLen - k步达到需要移动区间的前一个节点，因为每删除一个结点需要知道其前驱指针

4. 循环之后，将原链表剩下的结点一起尾插到结果链表中，并且需要将结果链表最后一个结点的next置为NULL，即使用暂存结点 resTail->next = NULL;

5. 返回的头节点应该是虚拟的前置结点的next指针


联系
我们