leetcode 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; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if (head == nullptr) { return ; } vector<ListNode *> vec; ListNode *node = head; while (node != nullptr) { vec.emplace_back(node); node = node->next; } int i = 0, j = vec.size() - 1; while (i < j) { vec[i]->next = vec[j]; i++; if (i == j) { break; } vec[j]->next = vec[i]; j--; } vec[i]->next = nullptr; } }; # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head: return ; ans = list() node = head while node: ans.append(node) node = node.next i, j = 0, len(ans) - 1 while i < j: ans[i].next = ans[j] i += 1 if i == j: break ans[j].next = ans[i] j -= 1 ans[i].next = None /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head){ if (head == NULL) { return head; } struct ListNode *node = head; int NodeNum = 0; struct ListNode *arr[40001]; node = head; NodeNum = 0; while (node != NULL) { arr[NodeNum++] = node; node = node->next; } int i = 0, j = NodeNum - 1; while (i < j) { arr[i]->next = arr[j]; i++; if (i == j) { break; } arr[j]->next = arr[i]; j--; } arr[i]->next = NULL; }

方法二：寻找链表中点 + 链表逆序 + 合并链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode *middleNode(ListNode *head) { ListNode *fast = head; ListNode *slow = head; while (fast->next != nullptr && fast->next->next != nullptr) { fast = fast->next->next; slow = slow->next; } return slow; } ListNode *reverseList(ListNode *head) { ListNode *preNode = nullptr; ListNode *curNode = head; ListNode *tmpNode = nullptr; while (curNode != nullptr) { tmpNode = curNode->next; curNode->next = preNode; preNode = curNode; curNode = tmpNode; } head = preNode; return head; } void mergeList(ListNode *root1, ListNode *root2) { ListNode *node1 = root1; ListNode *node2 = root2; ListNode *tmpNode1 = nullptr; ListNode *tmpNode2 = nullptr; while (node1 != nullptr && node2 != nullptr) { tmpNode1 = node1->next; tmpNode2 = node2->next; node1->next = node2; node1 = tmpNode1; node2->next = node1; node2 = tmpNode2; } } void reorderList(ListNode* head) { if (head == nullptr) { return ; } ListNode *mid = middleNode(head); ListNode *firstPart = head; ListNode *secondPart = mid->next; mid->next = nullptr; secondPart = reverseList(secondPart); mergeList(firstPart, secondPart); } }; # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: ListNode) -> None: """ Do not return anything, modify head in-place instead. """ if not head: return ; def middleNode(head: ListNode) ->ListNode: fastNode = head slowNode = head while fastNode.next and fastNode.next.next: fastNode = fastNode.next.next slowNode = slowNode.next return slowNode def reverseList(head: ListNode) ->ListNode: preNode = None curNode = head while curNode: tmpNode = curNode.next curNode.next = preNode preNode = curNode curNode = tmpNode head = preNode return head def mergeList(root1: ListNode, root2: ListNode) ->None: node1 = root1; node2 = root2; while node1 and node2: tmpNode1 = node1.next tmpNode2 = node2.next node1.next = node2 node2.next = tmpNode1 node1 = tmpNode1 node2 = tmpNode2 midNode = middleNode(head) firstList = head secondList = midNode.next midNode.next = None secondList = reverseList(secondList) mergeList(firstList, secondList)