本文共 1294 字,大约阅读时间需要 4 分钟。
题目:
解法1:
先求出字符串长度,然后依次把后面的字符串插入到前面中。
超时。
代码:
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };class Solution {public: void reorderList(ListNode *head) { if (head == NULL) return ; ListNode *temp = head->next; ListNode *last = head; int n = 0; while (temp) { ++n; temp = temp->next; } ListNode *now = head; while (n > 1) { int i = n; temp = now; while (i) { last = temp; temp = temp->next; --i; } last->next = NULL; temp->next = now->next; now->next = temp; now = temp->next; n -= 2; } }};解法2:
先将字符串分为等两段。
逆序后一段。
合并两段。
代码:
class Solution {public: void reorderList(ListNode *head) { if (head == NULL) return ; int len = 0; ListNode *temp = head; while (temp) { ++len; temp = temp->next; } int half = len - len / 2; temp = head; while (half != 1) { --half; temp = temp->next; } ListNode *head2 = temp->next; temp->next = NULL; if (head2 == NULL) return; ListNode *cur = head2->next; head2->next = NULL; ListNode *post = head2; while (cur) { temp = cur->next; cur->next = post; post = cur; cur = temp; } head2 = post; cur = head; while (head2) { temp = head2->next; head2->next = cur->next; cur->next = head2; cur = head2->next; head2 = temp; } }};
转载地址:http://dutsi.baihongyu.com/