大家好呀，今天为大家带来的LeetCode的题目是LeetCode 143.重排链表。
题目
分析
由于需要实际的进行节点交换而不是单纯改变节点内部的值，所以需要我们按照规律找到每个节点的需要的后续节点，但是由于链表不支持下标访问，所以一种方法就是利用线性表来存储该链表。或者是先找到原链表的中点，然后将原链表右半段反转，然后将其合并。
解法一：转为线性表
思路较为简单，首先遍历该链表，将该链表的节点用线性表存储起来。然后再重排链表
解法二：寻找链表中点、链表逆序、合并链表
由于目标链表即为原链表的左半端和反转后的右半端合并后的结果，所以我们要分为三步来进行重排链表
找到原链表中点：快慢指针将右半端反转：迭代法将原链表的两端合并
代码实现
解法一：
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
解法二：
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next = null;
l2 = reverseList(l2);
mergeList(l1, l2);
}
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public void mergeList(ListNode l1, ListNode l2) {
ListNode l1_tmp;
ListNode l2_tmp;
while (l1 != null && l2 != null) {
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
最后
如果觉得看完有收获，希望能给我点个赞，这将会是我更新的最大动力，感谢各位的支持欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。
