题目：
示例：
思路：
这题我们将使用栈解决这个问题，利用栈先进后出的特点，从链表的中间位置进行入栈，寻找链表的中间位置参考：删除链表的中间节点，之后从头开始进行连接。
本题使用的栈源代码在此处：栈和队列的实现
图示：
代码:
//栈 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef struct ListNode* DataType; typedef struct Stack { DataType* data; int top; int capacity; }Stack; void Init(Stack *st); void Push(Stack* st, DataType x); void Pop(Stack* st); DataType GetTop(Stack* st); bool Empty(Stack* st); void Init(Stack* st) { assert(st); st->data = NULL; st->top = 0; st->capacity = 0; } void Push(Stack* st, DataType x) { assert(st); if (st->capacity == st->top) { int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2; DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } st->data = temp; st->capacity = newcapacity; } st->data[st->top++] = x; } void Pop(Stack* st) { assert(st); assert(st->top > 0); st->top--; } DataType GetTop(Stack* st) { assert(st); assert(st->top > 0); return st->data[st->top - 1]; } bool Empty(Stack* st) { assert(st); return (st->top == 0); } //寻找链表的中间位置 struct ListNode* findMiddle(struct ListNode* head) { if(head == NULL || head->next == NULL) return NULL; struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } //于此处开始正式解题 void reorderList(struct ListNode* head) { if(head == NULL || head->next == NULL) return head; Stack list; Init(&list); struct ListNode* middle = findMiddle(head); while(middle) { Push(&list,middle); middle = middle->next; } struct ListNode* cur = head; struct ListNode* next = NULL; int flag = 1; while(!Empty(&list)) { if(flag == 1) { next = cur->next; cur->next = GetTop(&list); Pop(&list); flag = 0; } else { cur->next = next; flag = 1; } cur = cur->next; } cur->next = NULL; return head; }
