力扣算法题-143.重排链表 C语言实现

题目

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list

思路

第一种思路：双重循环，每次寻找末尾节点都重新遍历一次 1、先获取链表长度，根据长度算出中点； 2、遍历到中点的所有节点，找出对应的末端节点，进行连接即可； 思路比较简单，用时较长；

第二种思路： 1、将节点存入数组中； 2、根据数组位置，重新连接链表； 思路比较简答，用时较短；

程序

思路1：不借助别的空间，每次寻找末尾节点都重新遍历一次

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head){ int i,iNodelen = 0; struct ListNode* node = head; struct ListNode* rnode = NULL; struct ListNode* next = NULL; /*获取链表长度*/ while(node != NULL){ iNodelen++; node = node->next; } /*若节点长度小于等于2，则直接返回*/ if(iNodelen <= 2) return; node = head; /*遍历节点到中点位置停止*/ for(i=1;(iNodelen-1)/2-i>=0;i++){ rnode = node; next = node->next; /*获取末端节点*/ for(int j=i;j<iNodelen-i+1;j++){ rnode = rnode->next; } node->next = rnode; rnode->next = next; node = next; } /*清空最后一个节点的指向*/ if(iNodelen-2*(i-1) == 1){ node->next = NULL; }else{ node->next->next = NULL; } }

思路2：借助数组，重建链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head){ int i,iNodelen = 0; struct ListNode* node = head; struct ListNode* rnode = NULL; struct ListNode* next = NULL; /*获取链表长度*/ while(node != NULL){ iNodelen++; node = node->next; } if(iNodelen <= 2) return; /*声明初始化数组*/ struct ListNode** a=malloc(sizeof(struct ListNode*)*iNodelen); /*数组赋值*/ node = head; for(i=0;node != NULL;i++){ a[i] = node; node=node->next; } /*依据数组重新连接链表*/ node = head; for(i=1;(iNodelen-1)/2-i>=0;i++){ next = node->next; node->next = a[iNodelen-i]; a[iNodelen-i]->next = next; node = next; } /*链表末尾指向置空*/ if(iNodelen-2*(i-1)==1){ node->next = NULL; }else{ node->next->next = NULL; } }