关于数据结构与算法:Linklist经典题目旋转链表双指针应用

38次阅读

共计 821 个字符,预计需要花费 3 分钟才能阅读完成。

旋转链表

题目形容
给你一个链表的头节点 head,旋转链表,将链表每个节点向右挪动 k 个地位。

题目作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetb…
题目起源:力扣(LeetCode)
题解作者:WildDuck
剖析思路

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
// 本题解中的 fast 指针不会比 slow 每次走快 N 步,只是比 slow 指针先登程,二者步调速度统一,用于造成一个区间
typedef struct ListNode* ListNode_pointer;

struct ListNode* rotateRight(struct ListNode* head, int k)
{if(head != NULL)
    {
        ListNode_pointer fast = head;
        ListNode_pointer slow = head;
        ListNode_pointer save_pointer = NULL;
        int list_length=1;
        while(fast->next != NULL)
        {
            fast = fast -> next;
            list_length = list_length+1;
        }
        k = k%list_length;
        fast = head;
        for(int i = 0; i<k;i++)
        {fast = fast->next;}
        
        while(fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        if(slow != fast)
        {
            save_pointer = slow;
            slow = slow ->next;
            fast->next = head;
            save_pointer->next = NULL;
        }
        else if (slow == fast)
        {slow = head;}
        return slow;
    }
    else return head;
    
    
}

正文完
 0