【Leetcode——重排链表】

一、重排链表

对于这道题，有两种思路：

思路1.

1.使用一个线性表，存储链表中的每个节点，然后按照题目的条件，来链接线性表的各个节点即可。

使用左下标和右下标来定位线性表中的节点。

1.先存储链表中的节点数据到线性表

void reorderList(struct ListNode* head)
{struct ListNode* tmp[100000];int tail = 0;struct ListNode*cur = head;1.把链表中的节点存储到线性表中while(cur){tmp[tail++] = cur;cur = cur->next;}int front = 0;//由于下标从0开始，故需要--tailtail--;while(front<tail){tmp[front++]->next = tmp[tail];tmp[tail--]->next = tmp[front];}//到这一步必须置空，否则出现自己的next指向自己，出现环状//并且需要是front的next置空，因为在循环中tail和front已经错过了。tmp[front]->next = NULL;return head;
}

2.循环条件是front < tail

时间复杂度为O(N)，空间复杂度为O(N)

思路2.

（1）找到链表的中间节点
（2）将链表中间节点开始之后的链表逆置
（3）将两个链表重新合并

（1）找链表的中间节点可以使用快慢指针来求出。
快指针一次走两步，慢指针一次走一步。

（2）链表逆置，有两种方法，一种方法是使用三指针，一种方法是使用头插。

三指针法：

（3）合并两个链表，合并链表，从两个链表的头节点开始链接。

struct ListNode *middleNode(struct ListNode*head)
{struct ListNode*fast = head,*slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}struct ListNode* reverseList(struct ListNode*head)
{struct ListNode*prev = NULL;struct ListNode*cur = head;while(cur){struct ListNode*next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;
}void mergeList(struct ListNode*head,struct ListNode*head2)
{struct ListNode*l2 = head2,*l1 = head;while(l1 && l2){struct ListNode*l1next = l1->next;struct ListNode*l2next = l2->next;l1->next = l2;l1 = l1next;l2->next = l1;l2 = l2next;}
}
void reorderList(struct ListNode* head)
{if (head == NULL || head->next == NULL){return;}//1.找中间节点struct ListNode *midnode = middleNode(head);//2.逆置中间节点之后的链表//3.按照题目合并链表struct ListNode*head2 = midnode->next;midnode->next = NULL;//把它置空，其实是把midnode纳入第一条链表中的最后一个节点了//对后半链表逆置head2 = reverseList(head2);mergeList(head,head2);   }

时间复杂度O(n)，空间复杂度O(1)

总结

两种方法各有好处，法1空间复杂度大，但是易于理解。
法2相对更难理解，但是空间复杂度小。