143. 重排链表

题目描述

给定一个单链表 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

解

思路：递归实现，每次将

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head){ if(head == NULL)return; int n = 1; struct ListNode* p = head; struct ListNode* p_prodecessor = p; while(p->next != NULL){ n++; p_prodecessor = p; p = p->next; } if(n == 1 || n == 2)return; else{ struct ListNode* q = head->next; head->next = p; p->next = q; p_prodecessor->next = NULL; reorderList(q); return; } }