算法|链表复习
2022-12-30 本文已影响0人
激扬飞雪
82. 删除排序链表中的重复元素 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
if (pre.next.val == pre.next.next.val) {
ListNode cur = pre.next;
while (cur != null && cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
pre.next = cur.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
}
24. 两两交换链表中的节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = head;
ListNode pre = dummy;
while (cur != null && cur.next != null) {
ListNode temp = cur.next;
ListNode next = temp.next;
//倒序
temp.next = cur;
cur.next = next;
pre.next = temp;
pre = cur;
cur = next;
}
return dummy.next;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode next = head.next;
ListNode temp = swapPairs(next.next);
next.next = head;
head.next = temp;
return next;
}
}
147. 对链表进行插入排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = head;
ListNode cur = pre.next;
while (cur != null) {
if (cur.val > pre.val) {
//不动
pre = cur;
cur = cur.next;
continue;
}
ListNode temp = dummy;
while (cur.val > temp.next.val) {
temp = temp.next;
}
//删除cur
pre.next = cur.next;
//插入cur
ListNode next = temp.next;
temp.next = cur;
cur.next = next;
cur = pre.next;
}
return dummy.next;
}
}
148. 排序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode megerList(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast != null && fast.next != null) {
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return megerList(l1, l2);
}
}
61. 旋转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) return head;
ListNode cur = head;
int n = 1;
while (cur.next != null) {
n++;
cur = cur.next;
}
ListNode tail = cur;
k = k % n;
if (k == 0) return head;
k = n - k - 1;
cur = head;
while (k-- > 0) {
cur = cur.next;
}
ListNode newHead = cur.next;
cur.next = null;
tail.next = head;
return newHead;
}
}
143. 重排链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode l2 = slow.next;
slow.next = null;
//反转l2
ListNode cur = l2;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur = pre;
while (cur != null && head != null) {
ListNode next2 = cur.next;
ListNode next1 = head.next;
cur.next = next1;
head.next = cur;
head = next1;
cur = next2;
}
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
ListNode dummy = new ListNode(-1);
dummy.next = head;
//寻找m的前一个结点
int num = m - 1;
ListNode pre = dummy;
while (num-- > 0) {
pre = pre.next;
}
System.out.println(pre.val);
//翻转列表
ListNode cur = pre.next;
ListNode oldHead = cur;
ListNode tempPre = null;
int count = n - m + 1;
System.out.println(count);
while (count-- > 0) {
ListNode next = cur.next;
cur.next = tempPre;
tempPre = cur;
cur = next;
}
pre.next = tempPre;
oldHead.next = cur;
return dummy.next;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
if (head == null || head.next == null) return head;
// write code here
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
if (pre.next.val == pre.next.next.val) {
ListNode cur = pre.next;
while (cur != null && cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
pre.next = cur.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
public boolean isHaveNode(ListNode head, int k) {
ListNode cur = head;
int num = 0;
while (cur != null) {
num++;
if (num == k) {
return true;
}
cur = cur.next;
}
return false;
}
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
//判断是否还有k个
if (!isHaveNode(cur, k)) {
return dummy.next;
}
//翻转k个节点
ListNode tempCur = cur;
ListNode tempPre = null;
int num = k;
while (num-- > 0) {
ListNode tempNext = tempCur.next;
tempCur.next = tempPre;
tempPre = tempCur;
tempCur = tempNext;
}
pre.next = tempPre;
cur.next = tempCur;
pre = cur;
cur = tempCur;
}
return dummy.next;
}
}
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
private ListNode mergeKLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
private ListNode mergeKLists(ArrayList<ListNode> list, int left, int right) {
if (left >= right) {
return list.get(left);
}
int mid = left + (right - left) / 2;
ListNode l1 = mergeKLists(list, left, mid);
ListNode l2 = mergeKLists(list, mid + 1, right);
return mergeKLists(l1, l2);
}
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.isEmpty()) return null;
return mergeKLists(lists, 0, lists.size() - 1);
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
ListNode fast = pHead;
while (k > 0 && fast != null) {
k--;
fast = fast.next;
}
if (k != 0) return null;
ListNode slow = pHead;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
private ListNode mergerList(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast != null && fast.next != null) {
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
pre.next = null;
ListNode l1 = sortInList(head);
ListNode l2 = sortInList(slow);
return mergerList(l1, l2);
}
}
import java.util.*;
public class Solution {
public static class ListNode {
int key;
int value;
ListNode pre;
ListNode next;
ListNode() {
}
ListNode(int key, int value) {
this(key, value, null, null);
}
ListNode(int key, int value, ListNode pre, ListNode next) {
this.key = key;
this.value = value;
this.pre = pre;
this.next = next;
}
}
private int capacity;
private ListNode head;
private ListNode last;
private HashMap<Integer, ListNode> hashMap;
public Solution(int capacity) {
// write code here
this.capacity = capacity;
head = new ListNode();
last = new ListNode();
head.next = last;
last.pre = head;
hashMap = new HashMap<>();
}
private void moveToHead(ListNode listNode) {
//删除listNode
ListNode preNode = listNode.pre;
ListNode nextNode = listNode.next;
preNode.next = nextNode;
nextNode.pre = preNode;
listNode.next = null;
listNode.pre = null;
addToHead(listNode);
}
private void addToHead(ListNode listNode) {
ListNode nextNode = head.next;
head.next = listNode;
listNode.pre = head;
listNode.next = nextNode;
nextNode.pre = listNode;
}
private ListNode removeTail() {
ListNode tailNode = last.pre;
ListNode preNode = tailNode.pre;
preNode.next = last;
last.pre = preNode;
tailNode.pre = null;
tailNode.next = null;
return tailNode;
}
public int get(int key) {
// write code here
if (!hashMap.containsKey(key)) {
return -1;
}
ListNode result = hashMap.get(key);
moveToHead(result);
return result.value;
}
public void set(int key, int value) {
// write code here
if (hashMap.containsKey(key)) {
//包含 更新值
ListNode listNode = hashMap.get(key);
listNode.value = value;
moveToHead(listNode);
} else {
//是新的值
if (hashMap.size() >= capacity) {
//超过了总的容量 移除最近不使用的值，即last的值
ListNode tailNode = removeTail();
hashMap.remove(tailNode.key);
}
//添加新元素
ListNode newNode = new ListNode(key, value);
addToHead(newNode);
hashMap.put(key, newNode);
}
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution solution = new Solution(capacity);
* int output = solution.get(key);
* solution.set(key,value);
*/
import java.util.*;
public class Solution {
public static class ListNode {
int val;
ListNode next;
ListNode() {
this(-1);
}
ListNode(int val) {
this(val, null);
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
//创建循环链表
ListNode cur = null;
ListNode head = null;
for (int i = 1; i <= n; i++){
ListNode newNode = new ListNode(i);
if (head == null) {
head = newNode;
cur = newNode;
} else {
cur.next = newNode;
cur = newNode;
}
}
ListNode test = head;
while (test != null) {
System.out.println(test.val);
test = test.next;
}
if (cur != null) {
cur.next = head;
}
System.out.print(cur.val + " " + cur.next.val);
//遍历循环链表
ListNode pre = cur;
cur = pre.next;
while (cur != null && cur.next != cur){
//查找m步的前一个节点
int count = m - 1;
while (count > 0) {
count--;
pre = pre.next;
}
//删除这个节点
ListNode delNode = pre.next;
pre.next = delNode.next;
delNode.next = null;
cur = pre.next;
}
return cur.val;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
if (head == null || head.next == null) return head;
// write code here
//奇数
ListNode oddCur = head;
//偶数
ListNode eventHead = head.next;
ListNode eventCur = eventHead;
while (eventCur != null && eventCur.next != null){
oddCur.next = eventCur.next;
oddCur = oddCur.next;
eventCur.next = oddCur.next;
eventCur = eventCur.next;
}
oddCur.next = eventHead;
return head;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
// write code here
//奇数
ListNode oddDummy = new ListNode(-1);
ListNode oddCur = oddDummy;
//偶数
ListNode eventDummy = new ListNode(-1);
ListNode eventCur = eventDummy;
int num = 0;
ListNode cur = head;
while (cur != null) {
num++;
if (num % 2 == 1) {
//奇数
oddCur.next = cur;
oddCur = oddCur.next;
} else {
//偶数
eventCur.next = cur;
eventCur = eventCur.next;
}
cur = cur.next;
}
eventCur.next = null;
oddCur.next = eventDummy.next;
return oddDummy.next;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode plusOne (ListNode head) {
// write code here
ListNode cur = head;
Stack<ListNode> stack = new Stack<>();
while (cur != null){
stack.push(cur);
cur = cur.next;
}
int flag = 1;
while (!stack.isEmpty()){
ListNode listNode = stack.pop();
int sum = listNode.val + flag;
listNode.val = sum % 10;
flag = sum / 10;
if (flag == 0) return head;
}
if (flag == 1) {
ListNode newHead = new ListNode(1);
newHead.next = head;
return newHead;
}
return head;
}
}
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
private int plus(ListNode head) {
if (head == null) return 1;
int result = plus(head.next);
if (head.val + result == 10) {
head.val = 0;
return 1;
} else {
head.val = head.val + result;
return 0;
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode plusOne (ListNode head) {
// write code here
int result = plus(head);
if (result == 1) {
ListNode newHead = new ListNode(1);
newHead.next = head;
return newHead;
}
return head;
}
}
