148.排序链表

/*
 * @lc app=leetcode.cn id=148 lang=typescript
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

class ListNode {
	val: number;
	next: ListNode | null;
	constructor(val?: number, next?: ListNode | null) {
		this.val = val === undefined ? 0 : val;
		this.next = next === undefined ? null : next;
	}
}

function sortList(head: ListNode | null): ListNode | null {
	let nodeArr: ListNode[] = []; // 定义数组，存放节点

	let current = head;
	while (current) {
		let tag: ListNode | null = null;
		if (current) {
			tag = current.next;
			current.next = null;
		}
		nodeArr.push(current);
		current = tag;
	}

	// 冒泡排序
	// for (let i = 0; i < nodeArr.length - 1; i++) {
	// 	for (let j = 0; j < nodeArr.length - 1 - i; j++) {
	// 		if (nodeArr[j].val > nodeArr[j + 1].val) {
	// 			// 交换
	// 			[nodeArr[j], nodeArr[j + 1]] = [nodeArr[j + 1], nodeArr[j]];
	// 		}
	// 	}
	// }
	let sortArr = mergeSort(nodeArr)
	console.log(sortArr);
	
    // 组合
	let result: ListNode | null = null;
	let currentNode: ListNode | null = null;
	sortArr.map(node => {
		if (result == null) {
			result = node;
		} else {
			if (currentNode) {
				currentNode.next = node;
			}
		}
		currentNode = node;
	});

	return result;
}

function mergeSort(nums: ListNode[]): ListNode[] {
	if (nums.length <= 1) return nums;
	// 拆分
	let mid = Math.floor(nums.length / 2);
	let left = nums.slice(0, mid);
	let right = nums.slice(mid);

	return merge(mergeSort(left), mergeSort(right));
}

// 合并
function merge(left: ListNode[], right: ListNode[]): ListNode[] {
	let result: ListNode[] = [];
	let leftIndex = 0,
		rightIndex = 0;

	// 遍历完左右两个数组
	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex].val < right[rightIndex].val) {
			result.push(left[leftIndex]);
			leftIndex++;
		} else {
			result.push(right[rightIndex]);
			rightIndex++;
		}
	}
	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

let tag1 = new ListNode(4);
let tag2 = new ListNode(2);
let tag3 = new ListNode(1);
let tag4 = new ListNode(3);

tag1.next = tag2;
tag2.next = tag3;
tag3.next = tag4;
sortList(tag1);
// @lc code=end