Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
难度：medium
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
ListNode prePtr = dummyHead;
ListNode ptr = head;
while(ptr != null && ptr.next != null) {
ListNode first = ptr, second = ptr.next;
ptr = ptr.next.next;
prePtr.next = second;
second.next = first;
prePtr = first;
}
prePtr.next = ptr;
return dummyHead.next;
}
}
Reverse Nodes in K-Group
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. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.
难度：hard
Solution: Two Pointers
首先用两个指针界定要reverse的范围，然后用两个指针reverse范围内的元素。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null || k == 1) {
return head;
}
ListNode dummyHead = new ListNode(0);
ListNode prePtr = dummyHead;
ListNode nextPtr = head;
while(nextPtr != null) {
ListNode first = nextPtr;
ListNode second = nextPtr;
for(int i = 1; i < k; ++i) {
second = second.next;
if(second == null) {
prePtr.next = nextPtr;
return dummyHead.next;
}
}
nextPtr = second.next;
second.next = null;
reverse(first);
prePtr.next = second;
prePtr = first;
}
return dummyHead.next;
}
private void reverse(ListNode head) {
ListNode ptr = null;
ListNode nextPtr = head;
while(nextPtr != null) {
head = head.next;
nextPtr.next = ptr;
ptr = nextPtr;
nextPtr = head;
}
}
}
Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
难度：medium
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummyHead = new ListNode(0);
ListNode ptr = dummyHead;
for(int i = 1; i < m; ++i) {
ptr.next = head;
ptr = head;
head = head.next;
}
ListNode p1 = head;
ListNode p2 = head;
ListNode reverseHead = null;
for(int i = m; i <= n; ++i) {
p2 = p1.next;
p1.next = reverseHead;
reverseHead = p1;
p1 = p2;
}
ptr.next = reverseHead;
head.next = p1;
return dummyHead.next;
}
}
Reorder List
Given a singly linked list L: L0?L1?…?Ln-1?Ln, reorder it to: L0?Ln?L1?Ln-1?L2?Ln-2?… You must do this in-place without altering the nodes' values.
难度：medium
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null) {
return;
}
ListNode fast = head;
ListNode slow = head;
ListNode prevPtr = head;
while(fast != null && fast.next != null) {
prevPtr = slow;
slow = slow.next;
fast = fast.next.next;
}
prevPtr.next = null;
prevPtr = null;
while(slow != null) {
fast = slow.next;
slow.next = prevPtr;
prevPtr = slow;
slow = fast;
}
ListNode dummyHead = new ListNode(0);
slow = prevPtr;
prevPtr = dummyHead;
while(slow != null || head != null) {
if(head != null) {
prevPtr.next = head;
prevPtr = head;
head = head.next;
}
if(slow != null) {
prevPtr.next = slow;
prevPtr = slow;
slow = slow.next;
}
}
head = dummyHead.next;
}
}
Insertion Sort List
Sort a linked list using insertion sort.
难度：medium
Solution: Insertion Sort
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummyHead = new ListNode(0);
ListNode ptr = dummyHead;
while(head != null) {
while(ptr.next != null && ptr.next.val < head.val) {
ptr = ptr.next;
}
ListNode temp = ptr.next;
ptr.next = head;
ptr = ptr.next;
head = head.next;
ptr.next = temp;
ptr = dummyHead;
}
return dummyHead.next;
}
}
Palindrome Linked List
Easy
Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space?
Solution: reverse list
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;
slow.next = null;
ListNode ptr = null;
while(fast != null) {
slow = fast;
fast = fast.next;
slow.next = ptr;
ptr = slow;
}
while(head != null && slow != null) {
if(head.val != slow.val) {
return false;
}
head = head.next;
slow = slow.next;
}
return true;
}
}