概述
主要是LeetCode上面常考的一些链表面试手撕题，一些太简单的就没有列出来，比如反转链表，找中间节点，找倒数第K个节点，这些都是基本操作，还是要掌握的，列出来的都是一些比较综合，难写一点的题目~
题目列表
- 重排链表
- 给单链表+1
- 复制带随机指针的链表
- 有序链表转二叉搜索树
- 两数相加
- 旋转链表
- 奇偶链表 【2】
- 环形链表：判断有环，找环路口 【2】
- 合并K个排序链表-堆/两两归并【2】
- 翻转K/不足K也翻转【2】
- 排序链表【4】
-
重排链表
一道题目，涉及链表找中点，翻转链表，链表合并
class Solution {public ListNode findMid(ListNode head){ListNode f = head, s = head;while(f != null && f.next != null){f = f.next.next;s = s.next;}return s;}public ListNode reverse(ListNode head){if(head == null || head.next == null) return head;ListNode newHead = reverse(head.next);head.next.next = head;head.next = null;return newHead;}public void merge(ListNode l1, ListNode l2){while(l1 != null && l2 != null){ListNode l1next = l1.next;ListNode l2next = l2.next;l1.next = l2;l2.next = l1next;l1 = l1next;l2 = l2next;}}public void reorderList(ListNode head) {ListNode midNode = findMid(head);ListNode head2 = midNode.next;midNode.next = null;ListNode l2 = reverse(head2);merge(head, l2);}}
给单链表加一
- 先找第一个非9节点
- 将非9节点后面的节点，全部置为0，因为后面数字一定全是9
- 注意999的情况 - 判断虚拟头结点有没有改变
class Solution { public ListNode plusOne(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = dummy; ListNode notNine = cur; while(cur != null){ if(cur.val != 9) notNine = cur; cur = cur.next; } notNine.val = notNine.val + 1; ListNode nine = notNine.next; while(nine != null){ nine.val = 0; nine = nine.next; } return dummy.val == 0 ? dummy.next : dummy; } }
复制带随机指针的链表
- 链表复制
- 点和边的复制
- 两个链表的拆分
class Solution {
public Node copyRandomList(Node head) {
//复制点
//复制点和复制边都要跳两个p = p.next.next
for(Node p = head; p != null; p = p.next.next){
Node p2 = new Node(p.val);
p2.next = p.next;
p.next = p2;
}
//复制边
for(Node p = head; p != null; p = p.next.next){
if(p.random != null){
p.next.random = p.random.next;
}
}
//拆分链表
Node dummy = new Node(-1); Node cur = dummy;
for(Node p = head; p != null; p = p.next){
Node q = p.next;
p.next = q.next;
cur.next = q;
cur = cur.next;
}
return dummy.next;
}
}
有序链表转换二叉搜索树
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
ListNode pre = head, s = head, f = head;
while(f != null && f.next != null){
pre = s;
f = f.next.next;
s = s.next;
}
pre.next = null;
TreeNode root = new TreeNode(s.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(s.next);
return root;
}
}
两数相加 II
先翻转
class Solution {
public ListNode reverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public ListNode addRTwo(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
int t = 0;
while(l1 != null || l2 != null || t != 0){
if(l1 != null){t += l1.val; l1 = l1.next;}
if(l2 != null){t += l2.val; l2 = l2.next;}
cur.next = new ListNode(t%10);
t /= 10;
cur = cur.next;
}
return dummy.next;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l1r = reverse(l1);
ListNode l2r = reverse(l2);
return reverse(addRTwo(l1r, l2r));
}
}
用两个栈
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stk1 = new Stack<>();
Stack<Integer> stk2 = new Stack<>();
while(l1 != null){ stk1.push(l1.val); l1 = l1.next;}
while(l2 != null){ stk2.push(l2.val); l2 = l2.next;}
ListNode dummy = new ListNode(-1);
int t = 0;
while(!stk1.isEmpty() || !stk2.isEmpty() || t != 0){
if(!stk1.isEmpty()) t += stk1.pop();
if(!stk2.isEmpty()) t += stk2.pop();
ListNode node = new ListNode(t % 10);
t /= 10;
node.next = dummy.next;
dummy.next = node;
}
return dummy.next;
}
}
旋转链表
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null) return null;
int n = 0;
ListNode tail = null;
for(ListNode p = head; p != null; p = p.next) {
if(p.next == null) tail = p;
n++;
}
if(k % n == 0) return head;
k %= n;
ListNode f = head, s = head;
for(int i = 0; i < k; i++){
f = f.next;
}
while(f.next != null){
f = f.next;
s = s.next;
}
ListNode newHead = s.next;
s.next = null;
tail.next = head;
return newHead;
}
}
奇偶链表
奇偶链表
两个指针分别链接一下即可
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode odd = new ListNode(-1);
ListNode eve = new ListNode(-1);
ListNode curodd = odd, cureve = eve;
for(int i = 1; head != null; head = head.next, i++){
if(i % 2 != 0){
curodd.next = head;
curodd = curodd.next;
}else{
cureve.next = head;
cureve = cureve.next;
}
}
cureve.next = null;
curodd.next = eve.next;
return odd.next;
}
}
排序奇数生偶数降低链表
在上面的基础上增加一个翻转，和合并即可
class Solution {
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode nextNode = head.next;
head.next = pre;
pre = head;
head = nextNode;
}
return pre;
}
public void merge(ListNode l1, ListNode l2){
while(l1 != null && l2 != null){
ListNode l1next = l1.next;
ListNode l2next = l2.next;
l1.next = l2;
l2.next = l1next;
l1 = l1next;
l2 = l2next;
}
}
public ListNode oddEvenList(ListNode head) {
ListNode odd = new ListNode(-1);
ListNode eve = new ListNode(-1);
ListNode curodd = odd, cureve = eve;
for(int i = 1; head != null; head = head.next, i++){
if(i % 2 != 0){
curodd.next = head;
curodd = curodd.next;
}else{
cureve.next = head;
cureve = cureve.next;
}
}
cureve.next = null;
curodd.next = null;
ListNode l2 = reverse(eve.next);
merge(odd.next, l2);
return odd.next;
}
}
环形链表
环形链表 - 判断环
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode f = head, s = head;
while(f != null && f.next != null){
f = f.next.next;
s = s.next;
if(f == s) return true;
}
return false;
}
}
环形链表 - 找环的路口
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode f = head, s = head;
while(f != null && f.next != null){
f = f.next.next;
s = s.next;
if(f == s) break;
}
if(f == null || f.next == null) return null;
s = head;
while(f != s){
f = f.next;
s = s.next;
}
return f;
}
}
合并K个升序链表
堆
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
for(ListNode node : lists){
if(node != null) pq.offer(node);
}
while(!pq.isEmpty()){
ListNode node = pq.poll();
cur.next = node;
cur = cur.next;
if(node.next != null) pq.offer(node.next);
}
return dummy.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 l, int r){
if(l == r) return lists[l];
else if(l + 1 == r) return mergeTwo(lists[l], lists[r]);
else{
int mid = l + r >> 1;
ListNode lnode = merge(lists, l, mid);
ListNode rnode = merge(lists, mid + 1, r);
return mergeTwo(lnode, rnode);
}
}
public ListNode mergeTwo(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val <= l2.val){
l1.next = mergeTwo(l1.next, l2);
return l1;
}else{
l2.next = mergeTwo(l1, l2.next);
return l2;
}
}
}
K 个一组翻转链表
不足K个不翻转
class Solution {
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode nextNode = head.next;
head.next = pre;
pre = head;
head = nextNode;
}
return pre;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, s = head, f = dummy;
while(f.next != null){
for(int i = 0; i < k && f != null; i++) f = f.next;
if(f == null) break;
ListNode later = f.next;
f.next = null;
reverse(s);
pre.next = f;
s.next = later;
pre = s;
f = s;
s = s.next;
}
return dummy.next;
}
}
不足K个的部分也翻转
class Solution {
public ListNode reverse(ListNode head){
ListNode pre = null;
while(head != null){
ListNode nextNode = head.next;
head.next = pre;
pre = head;
head = nextNode;
}
return pre;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, s = head, f = dummy;
while(f.next != null){
for(int i = 0; i < k && f != null; i++) f = f.next;
if(f == null) {
if(s == null) break;
ListNode tail = reverse(s);
pre.next = tail;
s.next = null;
break;
}
ListNode later = f.next;
f.next = null;
reverse(s);
pre.next = f;
s.next = later;
pre = s;
f = s;
s = s.next;
}
return dummy.next;
}
}
排序链表
归并排序
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = head, f = head, s = head;
while(f.next != null && f.next.next != null){
pre = s;
f = f.next.next;
s = s.next;
}
ListNode head2 = pre.next;
pre.next = null;
ListNode l = sortList(head), r = sortList(head2);
return mergeTwo(l, r);
}
public ListNode mergeTwo(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val <= l2.val){
l1.next = mergeTwo(l1.next, l2);
return l1;
}else{
l2.next = mergeTwo(l1, l2.next);
return l2;
}
}
}
快排排序
class Solution {
public ListNode getTail(ListNode head){
while(head.next != null) head = head.next;
return head;
}
public int getMidValue(ListNode head){
ListNode f = head, s = head;
while(f != null && f.next != null){
f = f.next.next;
s = s.next;
}
return s.val;
}
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode l = new ListNode(-1), m = new ListNode(-1), r = new ListNode(-1);
ListNode ltail = l, mtail = m, rtail = r;
int x = getMidValue(head);
while(head != null){
if(head.val < x){
ltail.next = head;
ltail = ltail.next;
}else if(head.val == x){
mtail.next = head;
mtail = mtail.next;
}else{
rtail.next = head;
rtail = rtail.next;
}
head = head.next;
}
ltail.next = null; mtail.next = null; rtail.next = null;
l.next = sortList(l.next);
r.next = sortList(r.next);
getTail(l).next = m.next;
getTail(l).next = r.next;
return l.next;
}
}
插入排序
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1);
//head为当前要安排的节点
while(head != null){
ListNode headNext = head.next;
ListNode p = dummy;
//找到第一个比当前要安排的节点大的节点p.next
//-----p->p.next->-----
//-----p->head->p.next->-----
while(p.next != null && p.next.val <= head.val) p = p.next;
head.next = p.next;
p.next = head;
head = headNext;
}
return dummy.next;
}
}
删除链表中的重复元素
删除排序链表中的重复元素 - 重复留一
删除过后，重复的元素只出现一次
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur.next != null){
if(cur.val == cur.next.val) cur = cur.next;
else cur = cur.next;
}
return head;
}
}
删除排序链表中的重复元素 - 重复不留
重复的元素一个不留
//dummy -> 1 ->2 ->3 -> 3....
// s f
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode s = dummy;
while(s.next != null){
ListNode f = s.next;
while(f != null && f.val == s.next.val) f = f.next;
if(s.next.next == f) s = s.next;
else s.next = f;
}
return dummy.next;
}
}
移除未排序链表中的重复节点 - 重复留一
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while(pre.next != null){
ListNode cur = pre.next;
while(cur.next != null){
if(pre.next.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
pre = pre.next;
}
return dummy.next;
}
}
移除未排序链表中的重复节点 - 重复不留
输入：[1, 2, 3, 4 , 5, 3, 6, 2, 1]
输出：[4, 5, 6]
在上面一题的基础上打一个标记判断有无重复即可
pre ->待判断(cur) -> cur.next
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
boolean f = false;
while(pre.next != null){
ListNode cur = pre.next;
while(cur.next != null){
if(pre.next.val == cur.next.val) { f = true; cur.next = cur.next.next;}
else cur = cur.next;
}
if(f == false){
pre = pre.next;
}else{
pre.next = pre.next.next;
f = false;
}
}
return dummy.next;
}
}
若有收获，就点个赞吧
0 人点赞
