public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode subDummy = dummy;
ListNode subHead = head;
int i = 1;
while(i++ < m){
subHead = subHead.next;
subDummy = subDummy.next;
}
while( m++ < n){
ListNode tmp = subHead.next;
subHead.next = tmp.next;
tmp.next = subDummy.next;
subDummy.next = tmp;
}
return dummy.next;
}
25 Reverse Nodes in k-Groups
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Like revers sublist
check the next k elements are valid
In while loop, just shift k-1 index, after that, shift foward preHead and tail 1 index
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
def isValid(node, count):
while node.next and count > 0:
count-=1
node = node.next
return count == 0
dummy = sub_dummy = ListNode(0)
dummy.next = head
while isValid(sub_dummy, k):
# reverse k nodes only needs k-1 moves
for _ in range(k-1):
tmp = head.next
head.next = tmp.next
tmp.next = sub_dummy.next
sub_dummy.next = tmp
sub_dummy = head
head = head.next
return dummy.next
143 Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
Find middle
reverse tail
merge (2 ways)
def reorderList(self, head: ListNode) -> None:
if not head or not head.next: return
# 2 pointer find to the end
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# reverse 2nd half list
mid = slow
tail = self.reverse(mid.next)
mid.next = None
# combine 2 list
cur = ListNode(0)
while head and tail:
cur.next = head
cur = cur.next
head = head.next
cur.next = tail
cur = cur.next
tail = tail.next
if head:
cur.next = head
def reverse(self, head):
dummy = ListNode(0)
dummy.next = head
while head.next:
tmp = head.next
head.next = tmp.next
tmp.next = dummy.next
dummy.next = tmp
return dummy.next
82 Remove all duplicates
要比較第一個node, head 退回成為dummy
public static ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while(head.next != null && head.next.next != null){
if (head.next.val == head.next.next.val){
int dup = head.next.val;
while(head.next != null && head.next.val == dup){
head.next = head.next.next;
}
}else{
head = head.next;
}
}
return dummy.next;
}
86 Partition
Partition linkedList based on value x, < on the left, >= on the right
Create left and right node, as well as 2 leftHead and rightHead dummy nodes.
public ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
ListNode leftHead = left;
ListNode rightHead = right;
while(head != null){
if(head.val < x){
left.next = new ListNode(head.val);
left = left.next;
}else{
right.next = new ListNode(head.val);
right = right.next;
}
head = head.next;
}
left.next = rightHead.next;
return leftHead.next;
}
Sort List
Use the merge sort
findMiddle and merge method
// return mid index at round(n/2)
private ListNode findMiddle(ListNode head){
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode left, ListNode right){
ListNode dummy = new ListNode(0);
ListNode iter = dummy;
while(left != null && right != null){
if (left.val > right.val){
iter.next = right;
right = right.next;
}else{
iter.next = left;
left = left.next;
}
iter = iter.next;
}
if (left != null){
iter.next = left;
}
if (right != null){
iter.next = right;
}
return dummy.next;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
//merge sort
ListNode mid = findMiddle(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
328. Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
