[leetcode题解]61. Rotate List(链表旋转)

题目中给定一个单链表和一个数字k,要求将链表循环右移k次,每次将最右边的元素移动到最左边。最简单的思路先找到最后的k个元素的起始位置,然后把这k个元素直接搬到链表最前面并插入即可(可以使用尾插法,当然也可以把最后一个元素记录下来,然后直接将整段插入)。但是这里k的值可能非常大,是链表长度的好几倍,我们要先处理下k值,我们需要的k值是对链表长度取余得到的值,所以这里先写一个方法求得链表的长度,然后k有个取余操作。类似的两个链表归并问题

python代码:

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        if head is None:
            return head
            
        #求得链表长度并对k进行一个取余操作
        len = self.length(head)
        k = k % len
        
        #双指针法求链表中倒数第k个元素的位置
        pre = ListNode(-1)
        pre.next = head
        q = pre
        p = head
        while p is not None and k > 0:
            p = p.next
            k = k - 1
        
        if p is None:
            return head
        
        while p is not None:
            p = p.next
            q = q.next
            
        #将后续的元素使用尾插法一次插入链表前端
        p = q.next
        q.next = None
        q = pre
        while p is not None:
            t = p.next
            p.next = q.next
            q.next = p
            q = p
            p = t
        return pre.next
        
    def length(self, head):
        len = 0
        while head is not None:
            len += 1
            head = head.next
        return len

c++代码:

class Solution {
public:
    //本文源:凌风技术站-iaccepted
    ListNode* rotateRight(ListNode* head, int k) 
    {
        if (head == NULL)return head;
        
        ListNode *pre = new ListNode(-1);
        pre->next = head;
        
        ListNode *p = head, *q = head;
        
        //求链表的总长度len
        int len = 0;
        while(p != NULL)
        {
            ++len;
            p = p->next;
        }
        
        p = head;
        k %= len;
        
        //两个指针的方法去链表中倒数第k个元素
        while(k > 0)
        {   
            q = q->next;
            --k;
        }
        
        if (q == NULL)return head;
        
        while(q->next != NULL)
        {
            p = p->next;
            q = q->next;
        }
        
        //将后面的整段插入链表的前端
        q->next = pre->next;
        pre->next = p->next;
        p->next = NULL;
        return pre->next;
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]61. Rotate List(链表旋转)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/87.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注