leetcoed 61. 旋转链表

Question

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

麻烦老师花点时间帮忙看看

//我的思路是每次操作将链表最后一个节点与头节点交换，循环k次
//我的代码当k=1时运行成功，其他时候则失败，下面是巡行结果
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        ListNode* dummyHead=new ListNode(-1);
        dummyHead->next=head；
       
        
        for(int i=0;i<k;i++){
        
            ListNode* pre=dummyHead;
            while(pre->next->next!=NULL){
            pre=pre->next;//pre是最后一个节点的前一个结点，之所以k次中每一次都找到新链表中的最后一个节点是因为我觉的每次最后一个节点都会变位置
        }
            ListNode* node2=pre->next;//最后一个节点，下面三行是交换操作
            pre->next=NULL;
            node2->next=head;
            dummyHead->next=node2;
            
            }
        
        ListNode* ret= dummyHead->next;
        delete dummyHead;
        return ret;
    }
};

Answer 1

liuyubobobo 2020-05-28 17:01:34

如果我没有理解错，你的程序的问题可以在小数据量下稳定复现。

课程中介绍了如何创建一个链表，来测试自己的程序。创建一个只包含 3 个数据的量表，选择 k = 2，实际单步跟踪一下，看看你的程序每一步变量中存储的都是什么？在哪里出错了？

debug 是计算机专业的基本功，也是训练自己编程思维，提高算法能力的重要方式，进步就在这个过程中哦。

如果 debug 到某一步，对程序的执行方式不理解，比如你觉得应该输出什么，实际却输出了什么，你不理解，可以再来问答区提问。请谅解，我无法做到所有同学编程除了 bug，把程序扔到问答区，就能自动调 bug，这不是问答区设立的目的。我也确实无法做到这一点。问答区是解答疑问的，不是调 bug 的。请谅解。

如果你需要参考代码，可以参考我的 Leetcode 题解代码仓：https://github.com/liuyubobobo/Play-Leetcode

继续加油！：）

• 提问者 高斯的盾 #1

  非常感谢！

• 提问者 高斯的盾 #2

  首先先谢谢老师  确实，上面我提问的方式不对
  其实这道题我主要不明白的地方是指针。
  
  老师我举一个例子：
  有一个链表：1->2->3->4
  我建立两个指针Node1指向1这个节点，node2指向4这个节点；
  然后我让1，4两个节点交换位置：4->2->3->1;（具体交换方法是分别找到两个节点的前一个结点，使其指针域的地址互换）
  
  那现在node1 和node2的指向如何呢？
  node1指向的是 1 这个节点还是 4 这个节点呢

• liuyubobobo 回复 提问者 高斯的盾 #3

  你的逻辑，不是把 4 和 1 交换位置，而是将 4 放到了 1 的前面。有问题是因为没有重置 head，把 4 放到 1 的前面，4 是新的 head，但是在你的逻辑里，1 仍然是 head。继续加油！：）