重排链表(C语言)

---

---

 

题目：

 示例：

---

 

 思路：

这题我们将使用栈解决这个问题，利用栈先进后出的特点，从链表的中间位置进行入栈，寻找链表的中间位置参考：删除链表的中间节点，之后从头开始进行连接。

本题使用的栈源代码在此处：栈和队列的实现

图示：

---

 

代码:

//栈
#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;
}

---

 

个人主页：Lei宝啊

愿所有美好如期而遇