Reverse a linked list
1. Reverse single-linked lists
Leetcode-cn.com/problems/re…
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur ! =null){
ListNode help = cur.next;
// pre cur help
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code2. A group of k reverse singly linked lists
Leetcode-cn.com/problems/re…
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode cur = head;
for(int i = 0 ; i < k ; i++){
if(cur == null) return head;
cur = cur.next;
}
ListNode newHead = reverse(head , cur);
head.next = reverseKGroup(cur , k);
return newHead;
}
ListNode reverse(ListNode head , ListNode end){
ListNode cur = head;
ListNode pre = null;
while(cur ! = end){ ListNode help = cur.next;//pre cur help
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code3. Reverse left to right singly linked list
Leetcode-cn.com/problems/re…
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// create a virtual header
ListNode dummy = new ListNode(-1);
dummy.next = head;
//2. Find the m-1 node that started the flip and save it with cur
ListNode cur = dummy;
for(int i = 1; i < m ; i++) cur = cur.next; // start from dummy node
// a is the MTH node
ListNode a = cur.next;
ListNode tail = cur.next; // Use tail to store this node. After flipping the tail, attach it to the previous list
//4. Flip the single linked list
ListNode pre = null;
ListNode help = null;
for(inti = m ; i <= n ; i++){ help = a.next; a.next = pre; pre = a; a = help; }//5. After flipping, pre is the head node, tail is the tail node, and help is the next node of the tail node.
cur.next = pre;
tail.next = help;
returndummy.next; }}Copy the code4. Swap linked list nodes in pairs
Leetcode-cn.com/problems/sw…
class Solution {
public ListNode swapPairs(ListNode head) {
//1. Verify data
if(head == null || head.next == null) return head;
//2. Define a virtual header with the next pointer to head
ListNode dummy = new ListNode(0);
dummy.next = head;
//3. Start flipping
ListNode cur = dummy;
// The last two nodes are not null because there are still two nodes that can be swapped
while(cur.next ! =null&& cur.next.next ! =null) {// Define two pointer locations
ListNode a = cur.next;
ListNode b = cur.next.next;
// Start the exchange
// cur a b
ListNode c = b.next;
cur.next = b;
b.next = a;
a.next = c;
cur = a;
}
returndummy.next; }}Copy the code5. Determine if it’s a palindrome list
Leetcode-cn.com/problems/pa…
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
// Find the midpoint of the fast and slow pointer
ListNode fast = head;
ListNode slow = head;
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
/ / missile for midpoint
ListNode a = slow.next;
slow.next = null;
ListNode newHead = reverse(a);
ListNode cur = head;
while(cur ! =null&& newHead ! =null) {if(cur.val ! = newHead.val)return false;
cur =cur.next;
newHead = newHead.next;
}
return true;
}
ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur ! =null){
ListNode help = cur.next;
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code6. Rearrange linked lists
Leetcode-cn.com/problems/re…
class Solution {
public void reorderList(ListNode head) {
if(head == null) return;
ListNode fast = head , slow = head;
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
ListNode a = reverse(slow.next);
slow.next = null;
ListNode b = head;
while(a ! =null&& b ! =null){
ListNode c = a.next;
ListNode d = b.next;
//a c
//b db.next = a; a.next = d; a = c; b = d; }}ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur ! =null){
ListNode help = cur.next;
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code7. Odd-even linked lists
Leetcode-cn.com/problems/od…
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode oddHead = head;
ListNode evenHead = head.next;
ListNode a = head;
ListNode b = head.next;
while(b ! =null&& b.next ! =null){
ListNode c = b.next;
ListNode d = c.next;
//a b c d
a.next = c;
b.next = d;
a = a.next;
b = b.next;
}
a.next = evenHead;
returnoddHead; }}Copy the code8. The first common node of both lists
Leetcode-cn.com/problems/li…
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode l1 = headA , l2 = headB;
while(l1 ! = l2){ l1 = l1 ==null ? headB : l1.next;
l2 = l2 == null ? headA : l2.next;
}
returnl1; }}Copy the code9. Rotate the list
Leetcode-cn.com/problems/ro…
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0) return head;
//1. Find the length of the list
int len = 1;
ListNode cur = head;
while(cur.next ! =null){
cur = cur.next;
len++;
}
//2. End to end, find x
cur.next = head;
k = k % len;
int x = len - k;
//3. Find the x node, which is the header to return
while(x > 0){
cur = cur.next;
x--;
}
ListNode res = cur.next;
cur.next = null;
returnres; }}Copy the codeMerge sort linked lists
5. Merge two sorted singly linked lists
Leetcode-cn.com/problems/me…
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1. Verify data
if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
// create a virtual header
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//3. The two Pointers move backwards. The node is small enough to end with a cur
while(l1 ! =null&& l2 ! =null) {if(l1.val < l2.val){
cur.next = new ListNode(l1.val);
cur = cur.next; //cur also moves back one
l1 = l1.next;
}else{
cur.next = newListNode(l2.val); cur = cur.next; l2 = l2.next; }}//4. The rest of the linked list can be directly connected, because it is already sorted
cur.next = l1 == null ? l2 : l1;
returndummy.next; }}Copy the code6. Merge k sorted single linked lists
Leetcode-cn.com/problems/me…
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//1. Create a small root heap
Queue<ListNode> heap = new PriorityQueue<>((a , b) -> (a.val - b.val));
//2. Place all headers in the heap, so that the top of the heap is the smallest
for(ListNode node : lists){
if(node ! =null) heap.add(node);
}
// create a virtual node
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//4. Keep popping the top node after cur and push the next node of the popping node into the heap again
while(! heap.isEmpty()){ ListNode minNode = heap.poll(); cur.next = minNode; cur = cur.next;if(minNode.next ! =null) heap.add(minNode.next);
}
returndummy.next; }}Copy the code6. Split linked lists
Leetcode-cn.com/problems/pa…
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) return head;
ListNode dummy1 = new ListNode(-1);
ListNode a = dummy1;
ListNode dummy2 = new ListNode(-1);
ListNode b = dummy2;
ListNode cur = head;
while(cur ! =null) {if(cur.val < x){
a.next = cur;
cur = cur.next;
a = a.next;
}else{
b.next = cur;
cur = cur.next;
b = b.next;
}
}
a.next = dummy2.next;
b.next = null;
returndummy1.next; }}Copy the codeThe fast or slow pointer finds the NTH node from the bottom
1. Delete the penultimate node of the linked list
Leetcode-cn.com/problems/re…
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while(n > 0){
fast = fast.next;
n--;
}
while(fast.next ! =null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
returndummy.next; }}Copy the code2. Find the middle node of the list – if there are two middle nodes, return the second middle node
Leetcode-cn.com/problems/mi…
class Solution {
If there are two intermediate nodes, return the second intermediate node.
public ListNode middleNode(ListNode head) {
if(head == null) return head;
ListNode fast = head;
ListNode slow = head;
while(fast ! =null&& fast.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
returnslow; }}Copy the codeList order
1. List merge sort
Leetcode-cn.com/problems/so…
class Solution {
public ListNode sortList(ListNode head) {
if(head == null) return head;
return mergeSort(head);
}
ListNode mergeSort(ListNode head){
//1. Recursive termination condition
if(head == null || head.next == null) return head;
//2
ListNode fast = head;
ListNode slow = head;
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
//3
ListNode r = mergeSort(slow.next);
slow.next = null;
//4. Sort recursively on the left
ListNode l = mergeSort(head);
//5. Merge two lists
return merge(l,r);
}
ListNode merge(ListNode l , ListNode r){
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l ! =null&& r ! =null) {if(l.val <= r.val){
cur.next = l;
l = l.next;
cur = cur.next;
}else{
cur.next = r;
r = r.next;
cur = cur.next;
}
}
cur.next = l == null ? r : l;
returndummy.next; }}Copy the codeRemoves duplicate elements from the linked list
1. Delete only one duplicate element
Leetcode-cn.com/problems/re…
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode cur = head;
while(cur.next ! =null) {if(cur.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
returnhead; }}Copy the code2. Delete all duplicate elements
Leetcode-cn.com/problems/re…
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
while(fast ! =null) {if(fast.next ! =null && fast.val == fast.next.val){
while(fast.next ! =null && fast.val == fast.next.val ) fast = fast.next;
slow.next = fast.next;
fast = fast.next;
}else{ fast = fast.next; slow = slow.next; }}returndummy.next; }}Copy the code