链表专题总结_傅里叶不想变换_的博客-程序员宅基地
链表专题
- 2. 两数相加
- 445. 两数相加 II 同 剑指 Offer II 025. 链表中的两数相加
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 22. 链表中倒数第k个节点
- 19. 删除链表的倒数第 N 个结点
- 合并两个链表(无序)
- 21. 合并两个有序链表
- 23.合并K个升序链表
- 206. 反转链表
- 92. 反转链表 II(反转部分链表)
- 24. 两两交换链表中的节点
- 25. K 个一组翻转链表
- 剑指 Offer 18.删除链表指定结点
- 83. 删除排序链表中的重复元素（重复元素只出现一次）
- 82. 删除排序链表中的重复元素（重复的元素不出现）
- 141.判断链表是否有环
- 142.寻找环的入口结点
- 剑指 Offer 52. 两条链表的第一个公共结点(相交链表)
- 剑指 Offer 35. 复杂链表的复制
- 234. 回文链表
- 876. 链表的中间结点
- 147. 对链表进行插入排序
- 剑指 Offer 06. 从尾到头打印链表
- 61. 旋转链表
- 143.重排链表
- 148.排序链表
- 328. 奇偶链表
- 328. 奇数位升序偶数位降序的链表
- 86. 分隔链表：小于x的节点在大于等于x的节点之前
2. 两数相加
注意，链表是逆序存放的，l1 = [2,4,3], l2 = [5,6,4], 输出 [7,0,8]，实际上是342 + 465 = 807，所以题目已经降低难度了，从链表头开始遍历就相当于从个位相加。
注意：判断条件是 || 而不是 && 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0，
将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如 987 + 23 = 987 + 023 = 1010，变成链表就是[7,8,9]和[3,2,0]
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
int carry = 0;
ListNode cur = new ListNode(0);
ListNode dum = cur;
while(l1 != null || l2 != null){
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(carry > 0){
cur.next = new ListNode(carry);
}
return dum.next;
}
}
也可以这么写，这样就不需要考虑最后的进位了
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
int carry = 0;
ListNode cur = new ListNode(0);
ListNode dum = cur;
while(l1 != null || l2 != null || carry > 0){
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
return dum.next;
}
}
445. 两数相加 II 同 剑指 Offer II 025. 链表中的两数相加
跟上一题不一样的是，这次是数字最高位位于链表开始位置，所以我们需要反转，故用栈来做，也可以自己反转链表。
注意点：头插法！！
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
while(l1 != null){
s1.push(l1.val);
l1 = l1.next;
}
while(l2 != null){
s2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while(!s1.isEmpty() || !s2.isEmpty() || carry > 0){
int x = s1.isEmpty() ? 0 : s1.pop();
int y = s2.isEmpty() ? 0 : s2.pop();
int sum = x + y + carry;
carry = sum / 10;
ListNode tmp = new ListNode(sum % 10);
sum /= 10;
// 头插法！！
tmp.next = head;
head = tmp;
}
return head;
}
}
自己反转链表的方法：将list1和list2反转，反转后跟上一题的做法一样。最后再将结果链表翻转。
class Solution {
public ListNode addTwoNumbers(ListNode list1, ListNode list2) {
ListNode l1 = reverse(list1), l2 = reverse(list2);
int carry = 0;
ListNode cur = new ListNode(0);
ListNode dum = cur;
while(l1 != null || l2 != null || carry > 0){
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
return reverse(dum.next);
}
ListNode reverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode cur = head;
ListNode pre = null;
while(cur != null){
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
}
剑指 Offer 06. 从尾到头打印链表
思路：1、栈
2.迭代翻转链表后依次添加
import java.util.ArrayList;
import java.util.ArrayDeque;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayDeque<ListNode> stack= new ArrayDeque<>();
ArrayList<Integer> res = new ArrayList<>();
if(listNode == null) return res;
while(listNode != null){
stack.push(listNode);
listNode = listNode.next;
}
while(!stack.isEmpty()){
ListNode cur = stack.pop();
res.add(cur.val);
}
return res;
}
}
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if(listNode == null) return res;
ListNode pre = null;
ListNode cur = listNode;
while(cur != null){
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
while(pre != null){
res.add(pre.val);
pre = pre.next;
}
return res;
}
}
剑指 Offer 22. 链表中倒数第k个节点
两种思路：1.快慢指针 2.求链表长度，长的链表先走 n - k 步，然后两个链表一起走。
fast 走 k-1 步，返回slow，注意判断 k <= 0 或者 k 是否大于链表长度。
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if(pHead == null || k <= 0) return null;
ListNode slow = pHead, fast = pHead;
while(k - 1 > 0){
fast = fast.next;
k--;
}
// fast == null说明 k 大于链表长度，返回 null
if(fast == null) return null;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if(pHead == null || pHead.next == null) return pHead;
ListNode cur = pHead;
int len = 0;
while(cur != null){
len++;
cur = cur.next;
}
if(len < k) return null;
for(int i = 0; i < len - k; i++){
pHead = pHead.next;
}
return pHead;
}
}
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length1 = getLength(pHead1), length2 = getLength(pHead2);
ListNode slow = pHead1, fast = pHead2;
while(length1 != length2){
if(length1 > length2){
slow = slow.next;
length1--;
}else{
fast = fast.next;
length2--;
}
}
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
int getLength(ListNode node){
int len = 0;
while(node != null){
len++;
node = node.next;
}
return len;
}
}
19. 删除链表的倒数第 N 个结点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dum = new ListNode(0, head);
ListNode slow = dum, fast = dum;
while(n-- > 0){
fast = fast.next;
}
// fast == null说明 n 大于链表长度，返回 null
if(fast == null) return null;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dum.next;
}
}
合并两个链表(无序)
public void merge(ListNode l1, ListNode l2){
ListNode l1_tmp = null, l2_tmp = null;
while(l1 != null && l2 != null){
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
21. 合并两个有序链表
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode l1 = list1, l2 = list2;
ListNode res = new ListNode(0), cur = res;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return res.next;
}
}
思路：mergeTwoLists表示把两个有序链表合并，我们现在只需要比较第一个结点，如果 l1.val < l2.val，那就合并mergeTwoLists(l1.next, l2)，l1只需要连上合并后的头结点，同时返回l1就OK
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
23.合并K个升序链表
思路：两两合并或者使用堆
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for(int i = 0; i < lists.length; i++){
res = merge(res, lists[i]);
}
return res;
}
ListNode merge(ListNode list1, ListNode list2){
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode l1 = list1, l2 = list2;
ListNode dum = new ListNode(0), cur = dum;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dum.next;
}
}
使用归并的思想
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int left, int right){
if(left == right){
return lists[left];
}
int mid = left + ( right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return merge2List(l1,l2);
}
public ListNode merge2List(ListNode l1, ListNode l2){
if(l1 == null){
return l2;
}else if(l2 == null){
return l1;
}else if(l1.val <= l2.val){
l1.next = merge2List(l1.next, l2);
return l1;
}else{
l2.next = merge2List(l1, l2.next);
return l2;
}
}
}
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// Queue<ListNode> pq = new PriorityQueue<>(); // 默认是小顶堆，但是要根据元素的值来进行排序，所以还是要重写比较器。
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
for(ListNode node : lists){
if(node != null){
pq.offer(node);
}
}
ListNode dum = new ListNode(0), cur = dum;
while(!pq.isEmpty()){
ListNode minNode = pq.poll();
cur.next = minNode;
cur = minNode;
if(minNode.next != null){
pq.offer(minNode.next);
}
}
return dum.next;
}
}
206. 反转链表
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode prev = null, cur = head;
while(cur != null){
ListNode nextNode = cur.next;
// 反转
cur.next = prev;
// 移动prev和cur
prev = cur;
cur = nextNode;
}
return prev;
}
}
想象一下，比如是1-2-3-4, reverseList是翻转以head为头的链表，传入head.next，就得到4-3-2，newHead就是4，而此时head是1，此时有一个环，即1连着2，剩下部分是4-3-2，所以head.next.next = head;实际上是让2连1，然后head.next置为null
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
92. 反转链表 II(反转部分链表)
prev代表要翻转结点的前一个结点，所以循环left-1次，第二个for循环应该是right-left次
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dum = new ListNode(0, head);
ListNode prev = dum;
for(int i = 0; i < left - 1; i++){
prev = prev.next;
}
ListNode cur = prev.next;
for(int i = left; i < right; i++){
ListNode nextNode = cur.next;
cur.next = nextNode.next;
nextNode.next = prev.next;
prev.next = nextNode;
}
return dum.next;
}
}
使用栈来做，定义序号idx，idx在left和right之间的入栈。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode p = head;
int idx = 1;
Stack<Integer> stack = new Stack<>();
while(p != null){
if(idx >= left && idx <= right){
stack.push(p.val);
}
p = p.next;
idx++;
}
idx = 1;
p = head;
while(p != null){
if(idx >= left && idx <= right){
p.val = stack.pop();
}
idx++;
p = p.next;
}
return head;
}
}
24. 两两交换链表中的节点
递归：终止条件：结点为空或者只有一个结点if(head == null || head.next == null)。假设是1,2,3,4，现在head就是1，newHead应该是2，最后返回的也应该是newHead。也就是
if(head == null || head.next == null) return head;
ListNode newHead = head.next;
// 逻辑处理
return newHead;
swapPairs的功能，交换节点并返回头结点。所以此时head，也就是1应该指swapPairs(newHead.next)，也就是1-4-3，最后来处理2这个结点，让2连1就可以。
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
25. K 个一组翻转链表
每次外层循环代表一个长度为k的子链表的整体翻转，如果节点总数不是 k 的整数倍，则最后剩余的节点将保持原有顺序。故总共进行 len / k次
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dum = new ListNode(0, head);
ListNode temp = head;
int len = 0;
while(temp != null){
len++;
temp = temp.next;
}
ListNode pre = dum, cur = head;
for(int i = 0; i < len / k; i++){
for(int j = 0; j < k - 1; j++){
ListNode nextNode = cur.next;
cur.next = nextNode.next;
nextNode.next = pre.next;
pre.next = nextNode;
}
pre = cur;
cur = cur.next;
}
return dum.next;
}
}
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode dum = new ListNode(-1);
dum.next = head;
ListNode pre = dum;
ListNode end = dum;
while(end.next != null){
for(int i = 0; i < k && end != null; i++){
end = end.next;
}
if(end == null){
break;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = start;
}
return dum.next;
}
ListNode reverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode dum = new ListNode(0);
ListNode pre = dum;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();
ListNode dum = new ListNode(0);
ListNode p = dum;
while(true){
ListNode temp = head;
int count = 0;
while(temp != null && count < k){
stack.push(temp);
temp = temp.next;
count++;
}
if(count != k){
break;
}
while(!stack.isEmpty()){
p.next = stack.pop();
p = p.next;
}
p.next = temp;
head = temp;
}
return dum.next;
}
}
剑指 Offer 18.删除链表指定结点
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) return null;
if (head.val == val) return head.next;
ListNode prev = new ListNode(-1);
prev.next = head;
ListNode cur = head;
while(cur != null){
if (cur.val == val){
prev.next = cur.next;
// 提前结束
return head;
}
prev = prev.next;
cur = cur.next;
}
return head;
}
}
83. 删除排序链表中的重复元素（重复元素只出现一次）
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode dum = new ListNode(0, head);
ListNode cur = head;
while(cur.next != null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dum.next;
}
}
82. 删除排序链表中的重复元素（重复的元素不出现）
public class Solution {
//前提是已经排序好的链表，故不用移动两个指针
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null||pHead.next==null) return pHead;
// 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况
ListNode dum = new ListNode(0);
//设置空指针，放置第一个和第二个相等的情况,现在这两个指针保证了不相等
dum.next = pHead;
ListNode pre = dum;
ListNode last = dum.next;
while(last!=null){
if(last.next!=null&&last.val==last.next.val){
// 找到最后的一个相同节点,必须保证两个指针内容不等
while(last.next!=null&&last.val==last.next.val){
last =last.next;
}
// pre结点指向last的后一个结点，然后移动last结点
pre.next = last.next;
last = last.next;
//last = last.next;
//pre.next = last;
}else{
pre = pre.next;
last = last.next;
}
}
return dum.next;
}
}
141.判断链表是否有环
tips：一般碰到快慢指针（慢指针走一步，快指针走两步，while循环条件中都是）
fast!= null && fast.next != null
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return true;
}
}
return false;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
142.寻找环的入口结点
先判断是否有环，有环之后 fast = head，然后slow和fast一起出发
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
// 空链表或者链表只有一个节点，返回null
if(pHead == null || pHead.next == null) return null;
ListNode slow = pHead, fast = pHead;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
// 判断是否有环
if(slow == fast){
fast = pHead;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
剑指 Offer 52. 两条链表的第一个公共结点(相交链表)
1.链表走到尽头后，变成另一个链表的头结点
2.求出两个链表的长度，让长的链表先走几步，然后一起走。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode dumA = headA, dumB = headB;
while(dumA != dumB){
if(dumA != null){
dumA = dumA.next;
}else{
dumA = headB;
}
if(dumB != null){
dumB = dumB.next;
}else{
dumB = headA;
}
}
//dumA 要么是空，要么是两链表的交点
return dumA;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode dumA = headA, dumB = headB;
while(dumA != dumB){
dumA = dumA == null ? headB : dumA.next;
dumB = dumB == null ? headA : dumB.next;
}
return dumB;
}
}
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length1 = getLength(pHead1), length2 = getLength(pHead2);
ListNode dumA = pHead1, dumB = pHead2;
while(length1 != length2){
if(length1 > length2){
dumA = dumA.next;
length1--;
}else{
dumB = dumB.next;
length2--;
}
}
while(dumA != dumB){
dumA = dumA.next;
dumB = dumB.next;
}
return dumA;
}
int getLength(ListNode node){
int lenth = 0;
while(node!= null){
lenth++;
node = node.next;
}
return lenth;
}
}
剑指 Offer 35. 复杂链表的复制
1.哈希表映射原结点和新结点，然后连成链表。
import java.util.HashMap;
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode cur = pHead;
while(cur != null){
map.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
cur = pHead;
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(pHead);
}
}
234. 回文链表
思路：1.栈 2.把链表复制到数组，双指针
3.快慢指针找到前半部分链表的尾节点->反转后半部分链表->判断是否回文->恢复链表->返回结果
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while(cur != null){
stack.push(cur);
cur = cur.next;
}
while(head != null){
if(head.val != stack.pop().val){
return false;
}
head = head.next;
}
return true;
}
}
class Solution {
public boolean isPalindrome(ListNode head) {
ArrayList<Integer> arr = new ArrayList<>();
ListNode cur = head;
while(cur != null){
arr.add(cur.val);
cur = cur.next;
}
int l = 0, r = arr.size() - 1;
while(l <= r){
if(arr.get(l).equals(arr.get(r))){
l++;
r--;
}else{
return false;
}
}
return true;
}
}
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
876. 链表的中间结点
如果有两个中间节点，返回第一个中间节点
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
如果有两个中间节点，返回第二个中间节点
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while(fast!= null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
147. 对链表进行插入排序
class Solution {
public ListNode insertionSortList(ListNode head) {
// 1. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
if(head == null){
return head;
}
// 2. 链表初始化操作
ListNode dummyHead = new ListNode(0); // 引入哑节点
dummyHead.next = head; // 目的是在head之前插入节点
ListNode lastSorted = head; // 维护lastSorted为链表已经排好序的最后一个节点并初始化
ListNode curr = head.next; // 维护curr 为待插入的元素并初始化
// 3. 插入排序
while(curr != null){
if(lastSorted.val <= curr.val){
// 说明curr应该位于lastSorted之后
lastSorted = lastSorted.next; // 将lastSorted后移一位,curr变成新的lastSorted
}else{
// 否则,从链表头结点开始向后遍历链表中的节点
ListNode prev = dummyHead; // 从链表头开始遍历 prev是插入节点curr位置的前一个节点
while(prev.next.val <= curr.val){
// 循环退出的条件是找到curr应该插入的位置
prev = prev.next;
}
// 以下三行是为了完成对curr的插入（配合题解动图可以直观看出）
lastSorted.next = curr.next;
curr.next = prev.next;
prev.next = curr;
}
curr = lastSorted.next; // 此时 curr 为下一个待插入的元素
}
// 返回排好序的链表
return dummyHead.next;
}
}
剑指 Offer 06. 从尾到头打印链表
/**
* 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 sortList(ListNode head) {
// 1、递归结束条件
if(head == null || head.next == null){
return head;
}
// 2、找到链表中间节点并断开链表 & 递归下探
ListNode midNode = findMiddle(head);
ListNode rightHead = midNode.next;
midNode.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 3、当前层业务操作（合并有序链表）
return merge(left, right);
}
// 找到链表中间节点（876. 链表的中间结点）
public ListNode findMiddle(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 合并两个有序链表（21. 合并两个有序链表）
public ListNode merge(ListNode head1, ListNode head2){
ListNode l1 = head1, l2 = head2;
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode dum = new ListNode(0);
ListNode cur = dum;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dum.next;
}
}
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) {
// 当链表长度不大于 1， 新链表将与原链表相同
if(k == 0 || head == null || head.next == null) return head;
ListNode node = head;
int len = 1;
// 找到最后一个节点
while(node.next != null){
len++;
node = node.next;
}
// 循环次数
int add = len - k % len;
// k 为 n 的倍数时，新链表将与原链表相同
if(add == len){
return head;
}
node.next = head;
// 找到要断开的节点
while(add-- > 0){
node = node.next;
}
// 新的链表头
ListNode res = node.next;
// 断开操作
node.next = null;
return res;
}
}
143.重排链表
两种方法：1.将链表加入一个ArrayList后使用双指针，注意最后断开，否则链表会成环
2. 获得中间节点 -> 中间节点之后的部分进行反转-> 合并
/**
* 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) {
ArrayList<ListNode> list = new ArrayList<>();
ListNode cur = head;
while(cur != null){
list.add(cur);
cur = cur.next;
}
cur = head;
int i = 0, j = list.size() - 1;
while(i < j){
list.get(i).next = list.get(j);
i++;
if(i == j){
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}
/**
* 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) return ;
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next = null;
l2 = reverse(l2);
merge(l1, l2);
}
// LeetCode 876
public ListNode middleNode(ListNode head){
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// LeetCode 206
public ListNode reverse(ListNode head){
ListNode pre = null, cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public void merge(ListNode l1, ListNode l2){
ListNode l1_tmp = null, l2_tmp = null;
while(l1 != null && l2 != null){
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
}
148.排序链表
优先队列实现
注意：最后可能会出现循环链表 比如4-2-1-3， 排完序后是1-2-3-4,但此时4还连着2，所以出现了循环链表
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
Queue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
ListNode p = head;
while(p != null){
pq.offer(p);
p = p.next;
}
ListNode ans = new ListNode(0);
ListNode temp = ans;
while(!pq.isEmpty()){
temp.next = pq.poll();
temp = temp.next;
}
// 不加这句会出现循环链表 比如4-2-1-3， 排完序后是1-2-3-4,但此时4还连着2，所以出现了循环链表
temp.next = null;
return ans.next;
}
}
class Solution {
public ListNode sortList(ListNode head) {
// 1、递归结束条件
if(head == null || head.next == null){
return head;
}
// 2、找到链表中间节点并断开链表 & 递归下探
ListNode midNode = findMiddle(head);
ListNode rightHead = midNode.next;
midNode.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 3、当前层业务操作（合并有序链表）
return merge(left, right);
}
// 找到链表中间节点（876. 链表的中间结点）
public ListNode findMiddle(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 合并两个有序链表（21. 合并两个有序链表）
public ListNode merge(ListNode head1, ListNode head2){
ListNode l1 = head1, l2 = head2;
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode dum = new ListNode(0);
ListNode cur = dum;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dum.next;
}
}
328. 奇偶链表
思路：设置两个一个奇数链表头(其实就是head)，一个偶数链表头(head.next)，奇连偶，偶连奇。一直循环，最后奇偶相连
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null) return null;
ListNode odd = head;
ListNode even = head.next, evenHead = head.next;
while(even != null && even.next != null){
// 奇连偶
odd.next = even.next;
// 更新位置
odd = odd.next;
// 偶连奇
even.next = odd.next;
even = even.next;
}
// 奇偶相连
odd.next = evenHead;
return head;
}
}
分别定义奇偶链表；
遍历原链表，将当前结点交替插入到奇链表和偶链表（尾插法）；
将偶链表拼接在奇链表后面，最后将偶链表的最后连上null
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode oddHead = new ListNode(0);
ListNode oddTail = oddHead;
ListNode evenHead = new ListNode(0);
ListNode evenTail = evenHead;
int len = 1;
while(head != null){
if(len % 2 == 0){
evenTail.next = head;
evenTail = evenTail.next;
}else{
oddTail.next = head;
oddTail = oddTail.next;
}
len++;
head = head.next;
}
oddTail.next = evenHead.next;
evenTail.next = null;
return oddHead.next;
}
}
328. 奇数位升序偶数位降序的链表
题目描述：一个链表，特点是奇数位升序偶数位降序，使得链表变成升序的
思路：
1、对链表按照奇偶划分，分为一个升序链表 一个降序链表
2、翻转降序链表
3、合并两个升序链表
class Solution {
public ListNode oddEvenLinkedList(ListNode head) {
.
// 将偶数链表拆分出来
ListNode evenHead = getEvenList(head);
// 逆序偶数链表
ListNode reEvenHead = reverse(evenHead);
// 合并奇偶链表
ListNode newHead = merge2List(head, reEvenHead);
return newHead;
}
public ListNode getEvenList(ListNode head) {
ListNode oddHead = new ListNode(0);
ListNode oddTail = oddHead;
ListNode evenHead = new ListNode(0);
ListNode evenTail = evenHead;
int len = 1;
while(head != null){
if(len % 2 == 0){
evenTail.next = head;
evenTail = evenTail.next;
}else{
oddTail.next = head;
oddTail = oddTail.next;
}
len++;
head = head.next;
}
evenTail.next = null;
oddTail.next = null;
return evenHead.next;
}
public ListNode reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
public ListNode merge2List(ListNode l1, ListNode l2){
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val <= l2.val){
l1.next = merge2List(l1.next, l2);
return l1;
}else{
l2.next = merge2List(l1, l2.next);
return l2;
}
}
}
86. 分隔链表：小于x的节点在大于等于x的节点之前
思路：两个链表，small和large，然后遍历链表，得到两个构造好的small和large链表
注意后续处理：samll链表的尾连上large链表的头，然后large链表尾指向null
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode large = new ListNode(0);
ListNode smallHead = small, largeHead = large;
ListNode temp = head;
while(temp != null){
if(temp.val < x){
small.next = temp;
small = small.next;
}else{
large.next = temp;
large = large.next;
}
temp = temp.next;
}
small.next = largeHead.next;
large.next = null;
return smallHead.next;
}
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
ArcGIS中使用Create Fishnet生成格网_creat fish怎么用-程序员宅基地
1. 如果单元格的宽和高定义为0，那么必须指定行与列的数目以及格网对角的坐标 2. 格网的范围可以手动输入，也可以引用已有数据为模板。如果输入一个模版，格网的起始坐标和Y轴的坐标就被自动填充了，但仍需要输入行与列的数目 3. 如果行列数被指定为0，那么必须定义格网对角的坐标 4. 如果单元格的宽与高被定义为0，那么根据行列数与对角的坐标，程序会自动计算单元格的大小 5. 如果定义了单元格的宽度和高度并输入行列数为0，则必须输入格网_creat fish怎么用
四年级打字计算机上册教案,2019四年级上信息技术教案(A)打字速度靠指法_泰山版教育.doc.docx...-程序员宅基地
课题教学目标重点难点一、创设情境， 激趣导入二、自主探究，合作学习9、打字速度靠指课型新授教师贾明慧课时1 课时法1、初步掌握左右手十个手指的键位分工，认识八个基准键。2、掌握手指定位基准键的操作。3、十个手指有分工，打字姿势有标准，通过实际的触摸、实践，掌握基准键。左右手十个手指的键位分工，认识八个基准键；手指定位基准键的操作教学过程二次备课大强打了一会儿字就喊：“不好啦，才打了一会儿字，就感觉...
支付宝APP&H5&PC支付-程序员宅基地
支付宝支付支付配置public class AlipayConfig { // 商户appid public static String APPID = ""; // 私钥 pkcs8格式的 public static String RSA_PRIVATE_KEY = ""; // 服务器异步通知页面路径 需http://或者https://格式的完整路径，不能加?id=123这类自定义参数，必须外网可以正常访问 public static String
Qt设置常见窗口背景色几种方式_qt设置窗口背景颜色-程序员宅基地
常见窗口背景色总结qt 常见设置QWidget 类型窗口背景色几种方式setStyleSheetui.widget->setStyleSheet("QWidget{background: black;}");setPalettesetPalette(QPalette(Qt::white));setAutoFillBackground(true));自定义窗口paintEventvoid MyWidget::paintEvent(QPainterEvent* event)_qt设置窗口背景颜色
使用开源人脸特征提取器进行脸部颜值评分-程序员宅基地
本文仅为模型应用实战，而非颜值研究，所得结果仅供娱乐，仅供参考。方法也仅供参考。一般而言，数据量越大，结果越接近正常人审美。由于本次数据量较小，故仅为实验。使用环境：ubuntu14.04，opencv3.2.0，dlib19.6，python2.7一、准备工作：1、下载dlib库，下载特征提取模型。该模型的作用是通过卷积神经网络产生128维的特征向量，用以代表这张脸。网络...
QT+OpenCv实现在410c开发板上实现视频目标追踪预研——目标跟踪算法选择_qt 目标跟踪控制系统-程序员宅基地
目标跟踪算法作为一种有着非常广泛的应用的算法，在航空航天、智能交通、智能设备等领域有着非常广泛的应用。本系列博客将教大家在410c开发板上基于linux操作系统环境，采用QT+Opencv来实现视频目标跟踪，本文将首先向大家介绍常用的粒子滤波视频目标跟踪算法，对其原理进行简单的分析，为后续进一步选择和应用算法实现目标跟踪提供基础。_qt 目标跟踪控制系统
随便推点
什么是SpringCloud？可以用于干什么？_springcloud是什么-程序员宅基地
浅谈SpringCloud 前言使用 Spring Boot 开发分布式微服务时，我们面临以下问题：关于微服务技术栈：什么是SpringCloud ?使用SpringCloud的优缺点SpringCloud常见问题服务注册和发现是什么意思？Spring Cloud 如何实现？SpringBoot和SpringCloud的区别？负载均衡的意义什么？什么是 Hystrix？它如何实现容错？什么是 Hystrix 断路器？我们需要它吗？什么是 Netflix Feign？它的优点是什么？什么是SpringClou_springcloud是什么
Gradle发布共享库——Gradle访问Jitpack私有库_gradle credentials-程序员宅基地
一、引言前面两篇：Gradle 发布共享库——如何通过Gradle发布java依赖库（jar）到 jitpack 公共仓库、Gradle 发布共享库——如何通过Gradle发布Android依赖库（aar）到 jitpack 公共仓库讲解如何gradle通过github发布依赖库到jitpack上，然后方便其它人使用，但这里有个情况，前面这两种方法github仓库都是public的，但如果我们想让自己的项目private，不想全部公开，只给得到授权的人使用，那么我们该怎么办呢？下面我们介绍下这种.._gradle credentials
权值线段树_csdn 权值线段树-程序员宅基地
权值线段树简介维护全局的值域信息，每个节点记录的是该值域的值出现的总次数。使用二分的思想（离散化的时候，需要用到）支持查询全局K小值，全局rank，前驱，后继等。单词操作时间复杂度为O(logn)空间复杂度为O(n)相对于平衡树的优势：代码简单，速度快劣势：值域较大时，我们需要离散化，变成离线数据结构（我认为的离线指的是不能更改插入之类的操作，只能进行查询）例题..._csdn 权值线段树
python怎么算列表的平方_总算明了python如何求平方-程序员宅基地
总算明了python如何求平方日期：2019-08-25 12:22:17浏览：341核心提示：打开电脑上的计算器一看，居然没法求平方，是不是就没办法了呢？用python就可以啦，那么python如何求平方呢？一起来了解下吧：python如何求平方1.计算乘方pow(4,3)#结果642.计算平方importnumpy打开电脑上的计算器一看，居然没法求平方，是不是就没办法了呢？用py..._python计算列表中每个项目的平方
java读取class 内容_解析Java Class 文件过程_nlp小白菜的博客-程序员宅基地
前言：身为一个java程序员，怎么能不了解JVM呢，倘若想学习JVM，那就又必须要了解Class文件，Class之于虚拟机，就如鱼之于水，虚拟机因为Class而有了生命。《深入理解java虚拟机》中花了一整个章节来讲解Class文件，可是看完后，一直都还是迷迷糊糊，似懂非懂。正好前段时间看见一本书很不错：《自己动手写Java虚拟机》，作者利用go语言实现了一个简单的JVM，虽然没有完整实现JVM的..._java读取class文件内容
(4)nginx:日志以及定时切割日志小例子_nginx 日志分割,不用重启-程序员宅基地
一 关于Nginx日志我们观察nginx安装目录下的nginx.conf可以看到如下类似信息 #access_log logs/host.access.log main;这说明 该server, 它的访问日志的文件是 logs/host.access.log ,使用的格式”main”格式.除了main格式,你可以自定义其他格式. m_nginx 日志分割,不用重启