leetcode - 链表
链表专题训练。
1、反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
if(head.next == null) return head;
ListNode temp = head.next;
head.next = null;
ListNode next = null;
while(temp != null) {
next = temp.next;
temp.next = head;
head = temp;
temp = next;
}
return head;
}
}2、反转链表2
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
if(head.next == null) return head;
ListNode start = head;
ListNode front = null;
int count = 1;
while(count != m) {
if(start != null) {
front = start;
start = start.next;
}
count++;
}
ListNode temp = start.next;
ListNode need = start;
start.next = null;
ListNode next;
while(temp != null && count != n) {
next = temp.next;
temp.next = start;
if(front != null) {
front.next = temp;
}
start = temp;
temp = next;
count++;
}
if(temp != null) {
need.next = temp;
}
if(m == 1) head = start;
return head;
}
3、对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null) return head;
if(head.next == null) return head;
ListNode current = head.next;
head.next = null;
ListNode next = current.next;
if(current.val > head.val) {
head.next = current;
current.next = null;
current = next;
next = next.next;
}
while (current != null || next != null) {
ListNode temp = findTargetPosition(current, head);
head = temp == null ? head : temp;
current = next;
if(current != null) {
next = next.next;
}
}
return head;
}
public ListNode findTargetPosition(ListNode current, ListNode head) {
ListNode node = head;
ListNode front = head;
while (node != null) {
if (node == head && node.val >= current.val) {
current.next = node;
node = current;
break;
} else if (node != head && node.val >= current.val) {
current.next = front.next;
front.next = current;
node = head;
break;
} else {
front = node;
node = node.next;
if(node == null) {
front.next = current;
current.next = null;
}
}
}
return node;
}
}4、合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
public class MergeTwoLists {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) return null;
ListNode a = l1;
ListNode b = l2;
ListNode temp = new ListNode(0);
ListNode root = temp;
while(a != null || b!= null) {
int x = b == null ? Integer.MAX_VALUE : b.val;
int y = a == null ? Integer.MAX_VALUE : a.val;
if(y > x) {
temp.next = b;
b = b.next;
temp = temp.next;
} else {
temp.next = a;
a = a.next;
temp = temp.next;
}
}
return root.next;
}
}
5、合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例：
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
public class MergeKLists {
public ListNode mergeKLists(ListNode[] lists) {
ArrayList<ListNode> arrayList = new ArrayList<>();
ListNode root = new ListNode(0);
ListNode temp = root;
for (ListNode elem: lists) {
while(elem != null) {
arrayList.add(elem);
elem = elem.next;
}
}
Collections.sort(arrayList, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (ListNode elem: arrayList) {
temp.next = elem;
temp = temp.next;
}
return root.next;
}
}6、K个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
> 示例 :
> 给定这个链表：1->2->3->4->5
> 当 k = 2 时，应当返回: 2->1->4->3->5
> 当 k = 3 时，应当返回: 3->2->1->4->5
> 说明 :
> 你的算法只能使用常数的额外空间。
> 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
public class ReverseKGroup {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null) return null;
int t = k;
int length = getLength(head);
int count = length / k;
int mod = length % k;
ListNode temp = head;
ListNode next = head.next;
ListNode start = new ListNode(0);
ListNode root = start;
while (count !=0) {
if(t!=0) {
temp.next = start.next;
start.next = temp;
temp = next;
if (temp != null) next = next.next;
t--;
} else {
t = k;
count--;
start = head;
head = temp;
}
}
if(mod != 0) {
while (temp != null){
start.next = temp;
temp = temp.next;
start = start.next;
}
}
return root.next;
}
public int getLength(ListNode head) {
int length = 0;
ListNode temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
}
