首页 > 代码库 > 剑指Offer13 链表倒数第K个结点

剑指Offer13 链表倒数第K个结点

 1 /************************************************************************* 2     > File Name: 13_KthNodeToTail.cpp 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年08月30日 星期二 15时32分25秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <stdlib.h>10 11 // 链表结构体12 struct ListNode13 {14     int val;15     ListNode* next;16 };17 18 // 构造链表19 ListNode* createList()20 {21     struct ListNode* head;22     struct ListNode* p;23     struct ListNode* q;24     head = p = (ListNode*)malloc(sizeof(ListNode));25     head->val = 0;26     27     for (int i = 1; i <= 10; ++i)28     {29         q = (ListNode*)malloc(sizeof(ListNode));30         q->val = i;31         p->next = q;32         p = q;33     }34     p->next = NULL;35     return head;36 }37 38 // 顺序输出链表39 void PrintList(ListNode* head)40 {41     if (head == NULL)42         return;43     ListNode* temp = head;44     printf("PrintList:\n");45     while (temp != NULL)46     {47         printf("%d ", temp->val);48         temp = temp->next;49     }50     printf("\n");51 }52 53 ListNode* FintKthNodeToTail(ListNode* head, int k)54 {55     if (head==NULL || k<=0)56         return NULL;57     58     ListNode* fast = head;59     ListNode* slow = head;60     61     for (int i = 0; i < k - 1; ++i)62     {63         fast = fast->next;64         if (fast == NULL)65         {66             printf("Overflow!\n");67             return NULL;68         }69     }70     71     while (fast->next != NULL)72     {73         slow = slow->next;74         fast = fast->next;75     }76     printf("Find: %d\n", slow->val);77     78     return slow;79 }80 81 int main()82 {83     ListNode* test = createList();84     PrintList(test);85     86     int k = 3;87     ListNode* find = FintKthNodeToTail(test, k);88     89     return 0;90 }

 

剑指Offer13 链表倒数第K个结点