牛客top100 - 自刷打卡day1

top100-打卡day1

- 链表
- - BM1反转链表
  - BM2链表内指定区间反转
  - BM3链表中的节点每k个一组翻转
  - BM4合并两个排序的链表
  - BM5合并k个已排序的链表
  - BM6判断链表中是否有环
  - BM7链表中环的入口结点
  - BM8链表中倒数最后k个结点
  - BM9删除链表的倒数第n个节点
  - BM10两个链表的第一个公共结点
  - BM11链表相加(二)
  - BM12单链表的排序
  - BM13判断一个链表是否为回文结构
  - BM14链表的奇偶重排
  - BM15 删除有序链表中重复的元素-I
  - BM16 删除有序链表中重复的元素-II

链表

BM1反转链表

反转链表_牛客题霸_牛客网 (nowcoder.com)

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {if (head == null)return head;ListNode pre = null;ListNode cur = head;while (cur !=  null && cur.next != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}cur.next = pre;return cur;}}

BM2链表内指定区间反转

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

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类*///        p   c   n//    2       4//1-->2-->3-->4-->5-->nullpublic ListNode reverseBetween (ListNode head, int m, int n) {int num = n - m;//2if (num <= 0 ) return head;ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy;while ((--m) != 0) {pre = pre.next;}ListNode lHead = pre;ListNode lCur = pre.next;ListNode cur = pre.next;while (num != 0) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;num--;}ListNode next = cur.next;cur.next = pre;lHead.next = cur;lCur.next = next;return dummy.next;}
}

BM3链表中的节点每k个一组翻转

链表中的节点每k个一组翻转_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/**** @param head ListNode类* @param k int整型* @return ListNode类*/public ListNode reverseKGroup (ListNode head, int k) {int m = k;// write code hereif (head == null) return head;ListNode pHead = head;for (int i = 0; i < k; i++) {if (pHead == null) {return head;}pHead = pHead.next;}ListNode pre = null;ListNode cur = head;while((m--) != 0) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}head.next = reverseKGroup(pHead, k);return pre;}
}

BM4合并两个排序的链表

合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1, ListNode list2) {ListNode l1 = list1;ListNode l2 = list2;ListNode dummy = new ListNode(-1);ListNode cur = dummy;while (l1 != null && l2 != null) {if (l1.val >= l2.val) {cur.next = l2;l2 = l2.next;cur = cur.next;} else {cur.next = l1;l1 = l1.next;cur = cur.next;}}if (l1 != null) {cur.next = l1;}if (l2 != null) {cur.next = l2;}return dummy.next;}
}

BM5合并k个已排序的链表

合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)

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 {public ListNode Merge(ListNode list1, ListNode list2) {ListNode l1 = list1;ListNode l2 = list2;ListNode dummy = new ListNode(-1);ListNode cur = dummy;while (l1 != null && l2 != null) {if (l1.val >= l2.val) {cur.next = l2;l2 = l2.next;cur = cur.next;} else {cur.next = l1;l1 = l1.next;cur = cur.next;}}if (l1 != null) {cur.next = l1;}if (l2 != null) {cur.next = l2;}return dummy.next;}public ListNode mergeKLists(ArrayList<ListNode> lists) {return divideMerge(lists, 0, lists.size() -1);}ListNode divideMerge(ArrayList<ListNode> lists, int left, int right){if(left > right ){return null;}if(left == right) {return lists.get(left);}int mid = left + right >> 1;return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));}
}

BM6判断链表中是否有环

判断链表中是否有环_牛客题霸_牛客网 (nowcoder.com)

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && slow != null) {if(fast.next != null) {fast = fast.next.next;}else{return false;}slow = slow.next;if(slow == fast) {return true;}}return false;}
}

BM7链表中环的入口结点

链表中环的入口结点_牛客题霸_牛客网 (nowcoder.com)

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {if(pHead.next == null) return null;ListNode fast = pHead;ListNode slow = pHead;while(fast != null && slow != null) {if(fast.next != null){fast = fast.next.next;}else{return null;}slow = slow.next;if(fast == slow) {break;}}if(fast == null || slow == null) return null;fast = pHead;while(fast != slow){fast = fast.next;slow = slow.next;}return slow;}
}

BM8链表中倒数最后k个结点

链表中倒数最后k个结点_牛客题霸_牛客网 (nowcoder.com)

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 hereListNode pre = pHead;ListNode cur = pHead;int tk = k;while (pre != null && (tk--) != 0) {pre = pre.next;}if(pre == null && tk > 0) return null;while(pre != null) {pre = pre.next;cur = cur.next;}return cur;}
}

BM9删除链表的倒数第n个节点

删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/**** @param head ListNode类* @param n int整型* @return ListNode类*/public ListNode removeNthFromEnd (ListNode head, int n) {// write code hereint tn = n;ListNode cur = new ListNode(-1);cur.next = head;ListNode pre = head;ListNode red = cur;while (pre != null && (--tn) != 0) {pre = pre.next;}if (pre != null && tn > 0) return null;while (pre.next != null) {pre = pre.next;cur = cur.next;}cur.next = cur.next.next;return red.next;}
}

BM10两个链表的第一个公共结点

两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode p1 = pHead1;ListNode p2 = pHead2;while(p1 != p2){p1 = p1 == null ? pHead2 : p1.next;p2 = p2 == null ? pHead1 : p2.next;}return p1;}
}

BM11链表相加(二)

链表相加(二)_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/**** @param head1 ListNode类* @param head2 ListNode类* @return ListNode类*/public ListNode reverseList(ListNode head) {if (head == null) return head;ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}public ListNode addInList (ListNode head1, ListNode head2) {// write code herehead1 = reverseList(head1);head2 = reverseList(head2);ListNode h1 = head1;ListNode h2 = head2;int pVal = 0;ListNode res = new ListNode(-1);ListNode rHead = res;while (h1 != null && h2 != null) {int val = h1.val + h2.val + pVal;pVal = val >= 10 ? val / 10 : 0;val = val % 10;res.next = new ListNode(val);res = res.next;h1 = h1.next;h2 = h2.next;}while (h1 != null) {int val = pVal + h1.val;pVal = val >= 10 ? val / 10 : 0;val = val % 10;res.next = new ListNode(val);res = res.next;h1 = h1.next;}while (h2 != null) {int val = pVal + h2.val;pVal = val >= 10 ? val / 10 : 0;val = val % 10;res.next = new ListNode(val);res = res.next;h2 = h2.next;}if(pVal != 0) {res.next = new ListNode(pVal);}return reverseList(rHead.next);}
}

BM12单链表的排序

单链表的排序_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/**** @param head ListNode类 the head node* @return ListNode类*/public ListNode sortInList (ListNode head) {// write code herePriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {public int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}});ListNode cur = head;while (cur != null) {queue.offer(cur);cur = cur.next;}ListNode res = new ListNode(-1);ListNode rHead = res;while (!queue.isEmpty()) {res.next = queue.poll();res = res.next;}res.next = null;return rHead.next;}
}

BM13判断一个链表是否为回文结构

判断一个链表是否为回文结构_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/*** * @param head ListNode类 the head* @return bool布尔型*/public ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}public boolean isPail (ListNode head) {if(head == null || head.next == null) return true;// write code hereListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode rHead = reverseList(slow);ListNode lHead = head;while(lHead != null && rHead != null) {if(lHead.val != rHead.val){return false;}lHead = lHead.next;rHead = rHead.next;}return true;}
}

BM14链表的奇偶重排

链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com)

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 hereListNode J = new ListNode(-1);ListNode O = new ListNode(-1);ListNode cj = J;ListNode co = O;ListNode cur = head;boolean flag = false;while(cur != null) {if(flag) {co.next = cur;co = co.next;flag = ! flag;}else{cj.next = cur;cj = cj.next;flag = ! flag;}cur = cur.next;}co.next = null;cj.next = O.next;return J.next;}
}

BM15 删除有序链表中重复的元素-I

删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com)

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) return head;// write code hereListNode dummy = new ListNode(-1);dummy.next = head; ListNode cur = head;ListNode next = cur.next;if(next == null) return head;while(next != null){if(cur.val == next.val){cur.next = next.next;}else{cur = next;}next = next.next;} return dummy.next;}
}

BM16 删除有序链表中重复的元素-II

删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/**** @param head ListNode类* @return ListNode类*/public ListNode deleteDuplicates (ListNode head) {// write code hereif (head == null) return null;ListNode pre = new ListNode(-1);pre.next = head;ListNode resHead = pre;ListNode cur = head;ListNode next = cur.next;if (next == null) return head;while (next != null) {if (cur.val == next.val) {while (next != null && cur.val == next.val) {next = next.next;}cur = next;if (next != null) {next = next.next;}pre.next = cur;} else {pre = cur;cur = next;next = next.next;}}return resHead.next;}
}