剑指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 ListNode
13 {
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:
");
45     while (temp != NULL)
46     {
47         printf("%d ", temp->val);
48         temp = temp->next;
49     }
50     printf("
");
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!
");
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
", 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 }