力扣 148. 排序链表 & 234. 回文链表
148题目描述:
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表。
解析:
1.快慢指针找出中间节点,分成两个链表
2.分别对两个链表进行归并排序
3.最后合并两个链表
Java:
class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode slow = head, fast = head.next, left, right;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
right =mergeSort(slow.next);
slow.next = null;
left = mergeSort(head);
return mergeList(left, right);
}
private ListNode mergeList(ListNode left, ListNode right) {
ListNode curr = new ListNode(0);
ListNode dummy = curr;
while(left != null && right != null) {
if(left.val < right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
if(left != null) {
curr.next = left;
}
if(right != null) {
curr.next = right;
}
return dummy.next;
}
}
JavaScript:
var sortList = function(head) {
return mergeSort(head);
function mergeSort(head) {
if(head === null || head.next === null) {
return head;
}
let slow = head, fast = head.next.next, left, right;
while(fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
right = mergeSort(slow.next);
slow.next = null;
left = mergeSort(head);
return mergeList(left, right);
}
function mergeList(left, right) {
let curr = new ListNode();
let dummy = curr;
while(left !== null && right !== null) {
if(left.val < right.val) {
curr.next = left;
left = left.next;
} else {
curr.next = right;
right = right.next;
}
curr = curr.next;
}
if(left !== null) {
curr.next = left;
}
if(right !== null) {
curr.next = right;
}
return dummy.next;
}
};
234题目描述:
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
解析:
1.首先运用快慢指针找出中间节点
2.反转中间节点之后的链表
3.分别对比从头节点和反转后链表的节点值
Java:
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
fast = resverse(slow);
while(fast != null) {
if(fast.val != head.val) {
return false;
}
head = head.next;
fast = fast.next;
}
return true;
}
private ListNode resverse(ListNode head) {
ListNode curr = head, pre = null;
while(curr != null) {
ListNode temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
}
JavaScript:
var isPalindrome = function(head) {
let fast = head, slow = head;
while(fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
fast = reverse(slow);
while(fast !== null) {
if(fast.val !== head.val) {
return false;
}
fast = fast.next;
head = head.next;
}
return true;
function reverse(head) {
let curr = head, pre = null;
while(curr !== null) {
let temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
};