-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0019.c
88 lines (83 loc) · 2.18 KB
/
q0019.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//
// q0019.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0019.h"
#include "../common.h"
//19. Remove Nth Node From End of List
//Medium
//1337
//105
//
//
//Given a linked list, remove the n-th node from the end of list and return its head.
//
//Example:
//
//Given linked list: 1->2->3->4->5, and n = 2.
//
//After removing the second node from the end, the linked list becomes 1->2->3->5.
//Note:
//
//Given n will always be valid.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p = head;
struct ListNode headNode = {0, NULL};
headNode.next = head;
struct ListNode *pOperateNode = &headNode;
int threshold = n - 1;
int count = 0;
while (p->next != NULL) {
p = p->next;
if (++count > threshold) {
pOperateNode = pOperateNode->next;
}
if (count == threshold) {
pOperateNode->next = head;
}
}
// printf("\noperationNodeValue %d",pOperateNode->val);
struct ListNode *pRecycleNode = pOperateNode->next;
// printf("recycleNode value %d",pRecycleNode->val);
if (pOperateNode->next == head) {
// printf("\n pOperateNode->next->value %d",pOperateNode->next->val);
head = head->next;
}
pOperateNode->next = pOperateNode->next->next;
free(pRecycleNode);
return head;
}
int question19(){
int listLen = 5;
struct ListNode headNode = {0, NULL};
struct ListNode *head = &headNode;
for (int i = listLen; i > 0; i--) {
struct ListNode *newNode = calloc(1, sizeof(struct ListNode));
newNode->val = i;
newNode->next = head->next;
head->next = newNode;
}
head = head->next;
struct ListNode *pHead = head;
for (int i = 0; i < listLen; i++) {
printf(" %d ",pHead->val);
pHead = pHead->next;
}
head = removeNthFromEnd(head, 5);
printf("\n");
for (int i = 0; i < listLen - 1; i++) {
printf(" %d ",head->val);
head = head->next;
}
return 0;
}