[2487] Remove Nodes From Linked List

偷吃步先來一下

用stack 存完int 結果再重新assign 回linked list，後面的當做不存在XD

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* removeNodes(struct ListNode* head) {

int *stack = calloc (100000, sizeof(int));

int idx = -1, count =0 ;

struct ListNode* ptr = head;

while (ptr!=NULL)

{

if (idx <0 || stack[idx] >= ptr->val) // push

stack[++idx] = ptr->val;

else //pop and remove and push

{

while (idx >=0 && stack[idx] < ptr->val)

idx--;

stack[++idx] = ptr->val;

}

ptr = ptr->next;

count++;

}

ptr = head;

for (int i=0; i<=idx; i++)

{

ptr->val = stack[i];

if (i < idx)

ptr = ptr->next;

else

ptr->next = NULL;

}

return head;

}

看別人都在用reverse，怎麼可能想的到！雖然想要好好的free掉被remove的node，但是速度會變慢XD 只好先mark 起來惹

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* reverse(struct ListNode* head)

{

struct ListNode *pre, *cur, *next;

pre = NULL;

cur = head;

while (cur != NULL)

{

next = cur->next;

cur->next = pre;

pre= cur;

cur = next;

}

return pre;

}

struct ListNode* removeNodes(struct ListNode* head) {

struct ListNode *ptr , *next;

struct ListNode *newHead;

ptr = reverse(head);

newHead = ptr;

while (ptr != NULL)

{

next = ptr->next;

while (next != NULL && next->val < ptr->val)

{

ptr->next = next->next;

// next->next = NULL;

// free (next);

next = ptr->next;

}

ptr = ptr->next;

}

ptr = reverse(newHead);

return ptr;

}

更難想到的recursive 版本Orz 一路recursive 下去，就會從最後一個開始檢查起

寫完以後,recursive 也沒有比較快啊搞毛 XD

struct ListNode* removeNodes(struct ListNode* head) {

if (head == NULL)

return head;

head->next = removeNodes(head->next);//ptr->next 8, ptr 3

if (head->next != NULL && head->next->val > head->val)

return head->next;

else

return head;

}