• 关键字:链表操作,单向链表、双指针
  • 难度:中
  • 前置知识:链表
  • 题目大意:对于一个链表,将其向右旋转k个单位。

题目描述

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.

解法

为了叙述的方便,在后文中用head表示给定链表的表头

这道题目等于说就是LC#19的加强版本,但是其本质问题仍然没有变化——只需要找到这个链表的倒数第k个元素,然后将从第k个元素开始的所有结点移到链表的开头即可。

对于单向链表的倒数第k个元素这个问题,我们其实存在着一个非常好的“双指针”算法:

  • 令ptr1, ptr2均指向head,然后令ptr2向后跳转k-1次,此时ptr指向了链表的第k个元素。
  • 不断令ptr1, ptr2同时向后跳转,直到ptr2指向了最后一个元素,此时不难发现,由于ptr1和ptr2之间相隔了k-2个元素,所以ptr1指向的就是倒数第k个元素

在实际处理中,我们通常会使ptr2向后跳转k次,这样最后我们拿到的就不是倒数第k个元素,而是倒数第k+1个元素,这样的处理是为了方便修改倒数第k+1个元素的next指针(如果ptr1指向倒数第k个元素的话,我们是无法获得倒数第k+1个元素的指针的)

在得到了倒数第k个元素之后,我们就可以通过几次简单的链表操作,完美的解决这个问题了。

值得注意的是,这题存在着许多的边界情况需要特殊处理,如Head为空,k>链表长度等等,需要小心的进行讨论与处理。

这道题目主要考察的是单向链表用于查找倒数第K个元素的“双指针”技巧,另外还对边界情况处理进行了一定程度的考察,本身的思维难度并不算太难,主要考察的是综合素质吧。

参考代码

/**
 * 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;
        // 统计链表长度并对k进行取余操作
        ListNode *tmp = head;
        int n = 1;
        while (tmp -> next) {
            n ++;
            tmp = tmp -> next;
        }
        k = k % n;
        if (k == 0) return head; // 边界情况处理
        // 寻找倒数第k+1个元素
        ListNode *ptr1 = head, *ptr2 = head;
        for (int i = 0; i < k; i++) ptr2 = ptr2 -> next;
        while (ptr2 -> next) {
            ptr1 = ptr1 -> next;
            ptr2 = ptr2 -> next;
        }
        // 将head开头的一段同ptr1开头的进行调换
        ListNode *newHead = ptr1 -> next;
        ptr1 -> next = NULL;
        ptr2 -> next = head;
        // 返回答案
        return newHead;
    }
};

登录发表评论 注册

反馈意见