首页 > 代码库 > LeetCode OJ 143. Reorder List(两种方法,快慢指针,堆栈)
LeetCode OJ 143. Reorder List(两种方法,快慢指针,堆栈)
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes‘ values.
For example,
Given {1,2,3,4}
, reorder it to {1,4,2,3}
.
Subscribe to see which companies asked this question
解答:
第一种方法是利用快慢指针找到中间节点,然后反转后半部分链表后合并链表,当然这里要注意分类讨论奇数个节点和偶数个节点的情况,另外注意合并链表后新链表的结尾要赋值为NULL,否则主函数中遍历链表就是在遍历循环链表了……还有就是一如既往地要注意空表的情况……
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head) { struct ListNode *fast = head, *slow = head, *tmp, *tmp_head = NULL, *tmp_tail; while(NULL != fast&&NULL != fast->next){ slow = slow->next; fast = fast->next->next; } if(NULL == fast){ tmp_tail = slow; } else{ tmp_tail = slow->next; } while(NULL != tmp_tail){ tmp = tmp_tail->next; tmp_tail->next = tmp_head; tmp_head = tmp_tail; tmp_tail = tmp; } slow = tmp_head; if(NULL == fast){ while(NULL != slow){ tmp = slow->next; slow->next = head->next; if(NULL == tmp){ slow->next = NULL; } head->next = slow; head = slow->next; slow = tmp; } } else{ while(NULL != slow){ tmp = slow->next; slow->next = head->next; head->next = slow; head = slow->next; slow = tmp; } head->next = NULL; } }
第二种方法是利用堆栈FILO,这样的话顺序遍历链表将节点压入堆栈后,节点依次弹出链表的顺序就和题中要求的顺序吻合了,而且压入堆栈的过程中还得到了链表长度……这里需要注意的还有就是变量的值在操作中可能会更改,需要用临时变量来保存当前值……
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head) { struct ListNode* stack[100000]; struct ListNode *tmp = head; int top = -1, size, tmp_val; while(NULL != tmp){ stack[++top] = tmp; tmp = tmp->next; } size = (top + 1) / 2; tmp_val = top; while(size){ size--; tmp = stack[top]; top--; tmp->next = head->next; head->next = tmp; head = tmp->next; } if(0 == tmp_val % 2){ head->next = NULL; } else if(NULL != tmp){ tmp->next = NULL; } }
LeetCode OJ 143. Reorder List(两种方法,快慢指针,堆栈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。