|
该文章是本人的第一篇，略有忐忑，不好，勿喷；有误，请指教，谢谢！ 这篇是一个来自leetcode的算法题，关于数据结构链表的，不算难，本文简略概述下解析过程及校对过程。 题目：旋转链表 示例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 示例2： 输入: 0->1->2->NULL, k = 4输出: 2->0->1->NULL解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL向右旋转 4 步: 2->0->1->NULL解题过程： 第一次解答代码： /** * 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) { ListNode* p = head; int num = 0; while((p!=NULL)&&(p->next != NULL)) { num++; p = p->next; } num++; if(p) p->next = head; int steps = 0; while(num < k) num += num; steps = num - k; for(int i = 0;i < steps;i++) { if(p) p = p->next; } ListNode* newhead = NULL; if(p) { newhead = p->next; p->next = NULL; } return newhead; } }; 第一次解析完成后，感觉信息满满，必能通过，谁知告知如下结果： 提示超出了执行时间超时~ 仔细观察，修改上述代码中的红色部分，进行了下面的解答。 第二次解答： class Solution { public: ListNode* rotateRight(ListNode* head, int k) { ListNode* p = head; int num = 0; while((p!=NULL)&&(p->next != NULL)) { num++; p = p->next; } num++; if(p) p->next = head; int steps = 0; steps = num - k % num; for(int i = 0;i < steps;i++) { if(p) p = p->next; } ListNode* newhead = NULL; if(p) { newhead = p->next; p->next = NULL; } return newhead; } }; 修改完红色部分后，提交，通过~ 备注：红色部分修改的是从原链表尾节点寻找新链表尾节点所需走的步数。 参考校验： 自己提交通过后，浏览了下别人的解答，发现有改进的地方，请看下文。 参考代码： class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head) return head; int len=1; // number of nodes ListNode *newH, *tail; newH=tail=head; while(tail->next) // get the number of nodes in the list { tail = tail->next; len++; } tail->next = head; // circle the link if(k %= len) { for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head) } newH = tail->next; tail->next = NULL; return newH; } }; 反观自己的代码，缺少了第一行的判断头节点是否为空，对照两份代码，可以看到，加上头节点的判空逻辑可以省略后面的多次判空。 附注解题思路： 1、寻找到原链表的尾节点，并同时计算链表长度 2、连接尾节点与头节点，即：尾节点的下一个节点为头节点，此时链表成环 3、计算新链表尾节点的位置（从原链表尾节点倒走k，则等同于正走n-k,n为链表长度，而如果n<k,则n=n+n,直到n>k） 4、从原链表的尾节点走第三步计算出的步数，即可得到新链表的尾节点 5、先标识出新链表的头节点，即：新链表的尾节点的下一个节点,之后断开环 |
|
|
