首页 > 代码库 > LeetCode: Reorder List

LeetCode: Reorder List

LeetCode: Reorder List

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-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}.

地址:https://oj.leetcode.com/problems/reorder-list/

算法:先把链表从中间节点分成两段,然后将后半部分的链表逆置,最后在将后半部分的链表按题目的要求插入原链表中。代码:

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     void reorderList(ListNode *head) {12         int num_node = 0;13         ListNode *p = head;14         while(p){15             ++num_node;16             p = p->next;17         }18         int half_num_node = (num_node + 1) / 2;19         p = head;20         ListNode *pre = NULL;21         for (int i = 0; i < half_num_node; ++i){22             pre = p;23             p = p->next;24         }25         if(pre) pre->next = NULL;26         pre = NULL;27         ListNode *half_head = NULL;28         while (p){29            pre = p;30            p = p->next;31            pre->next = half_head;32            half_head = pre;33         }34         p = head;35         while(half_head){36             pre = half_head;37             half_head = half_head->next;38             pre->next = p->next;39             p->next = pre;40             p = p->next->next;41         }42     }43 };