题目链接

注意点

k可能会大于链表长度

解法

解法一：首先遍历一遍链表得到链表的长度，k对其取余数。然后设置快慢指针，快指针先走k步，然后快慢指针一起走，当快指针走到底的时候，慢指针也走到了新的链表头结点的前一个结点，这时候修改快慢指针的指向就好了。时间复杂度O(n)。

/** * 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 == NULL) return head;        int i,n = 0;        ListNode* p = head;        while(p != NULL)        {            p = p ->next;            n++;        }        //cout << n;        k %= n;        ListNode* fast = head;        ListNode* slow = head;        while(k > 0)        {            fast = fast->next;            k--;        }        //if(fast == NULL) return head;        while(fast->next != NULL)        {            fast = fast->next;            slow = slow->next;        }        fast->next = head;        fast = slow->next;        slow->next = NULL;        return fast;    }};

解法二：同样首先遍历一遍链表得到链表的长度，k对其取余数。将链表尾和链表头相连，然后继续往后遍历（也就是从头开始）n-k个结点，这时正好指向新的链表头结点的前一个结点。时间复杂度O(n)

/** * 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 == NULL) return head;        int i,n = 1;        ListNode* p = head;        while(p->next != NULL)        {            p = p ->next;            n++;        }        p->next = head;        k %= n;        for(i = 0;i < n-k;i++) p = p->next;        ListNode* ret = p->next;        p->next = NULL;        return ret;    }};

小结

链表题

转载于:https://www.cnblogs.com/multhree/p/10443859.html

你可能感兴趣的文章