重排链表(C语言)-Toy模板网

这篇具有很好参考价值的文章主要介绍了重排链表(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

重排链表(C语言),C语言,数据结构,链表,数据结构,leetcode

题目：

重排链表(C语言),C语言,数据结构,链表,数据结构,leetcode

示例：

重排链表(C语言),C语言,数据结构,链表,数据结构,leetcode

思路：

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

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

图示：

重排链表(C语言),C语言,数据结构,链表,数据结构,leetcode

代码:

//栈
#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宝啊

愿所有美好如期而遇文章来源地址https://www.toymoban.com/news/detail-670631.html

到了这里，关于重排链表(C语言)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！