南京网站制作招聘网,博物馆网站建设方案书,濮阳建设网站,wordpress 登录信息题目#xff1a; 示例#xff1a; 思路#xff1a;
这题我们将使用栈解决这个问题#xff0c;利用栈先进后出的特点#xff0c;从链表的中间位置进行入栈#xff0c;寻找链表的中间位置参考#xff1a;删除链表的中间节点#xff0c;之后从头开始进行连接。
本题使用… 题目 示例 思路
这题我们将使用栈解决这个问题利用栈先进后出的特点从链表的中间位置进行入栈寻找链表的中间位置参考删除链表的中间节点之后从头开始进行连接。
本题使用的栈源代码在此处栈和队列的实现
图示 代码:
//栈
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef 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宝啊
愿所有美好如期而遇
