LeetCode

LeetCode-61 旋转链表

nkul · 9月7日 · 2020年 27次已读
  • k可能很大,但每移动n(n为链表长度)又恢复原序,因此实际右移的是k%n步
  • 将后k个移动到链表首部即可,因此需要修改三个节点
    • 倒数第k+1节点
    • 倒数第k个节点
    • 尾结点
  • 修改为:
    • 尾结点指向头
    • 头节点指向倒数第k
    • 倒数第k+1指向空
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || k == 0) return head;

        //计算链表长度和尾结点!
        int n = 0;
        ListNode* tail ; 
        for(auto p = head;p; p = p->next){
            tail = p;
            n++;
        }
        
        k = k % n;

        ListNode* q = head;
        ListNode* kth  = getKth(q,k,n);
        tail->next = head;
        head = kth->next;
        kth->next = NULL;
        return head;

    }

    //辅助函数,找到倒数第k+1(即正数l-k)个节点
    ListNode* getKth(ListNode* head , int k , int l){
       for(int i=0;i < l-k-1  ;i++){
           head = head->next;
       } 
       cout<val;
       return head;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!