【数据结构】:大厂面试经典链表OJ题目详解
反转链表
206. 反转链表 - 力扣(LeetCode)
思路解透
本题就是通过不停地将最先的 head
节点位置的后一位插到最前面,完成链表的反转
本题需要两个节点变量
cur
:其任务就是定位到原head
节点位置的前一位,然后将自己插入到当前head
节点的前面- 因为链表的最后一个节点都是指向一个
null
值,所以需要将最先的head
节点的next
置为空 - 但在将
head.next
置为null
之前,需要先将cur
节点实例化出来,不然cur
就无法找到原先的head
节点的位置了
- 因为链表的最后一个节点都是指向一个
curN
:其任务就是定位到cur
的后一个节点,方便让cur
进行循环插入- 其在循环中进行实例化,因为每一次插入完成之后,
curN
的位置都是需要随着cur
的改变而改变 curN
实例化为cur
的下一个节点。在cur
插入完成后,cur
就会定位到curN
的位置,若此为止不为null
,则继续进行前插
- 其在循环中进行实例化,因为每一次插入完成之后,
代码解析
class Solution {public ListNode reverseList(ListNode head) {//1. 防止空指针异常 if(head == null){ return head; } //2. 将head.next置为空 //注意先把 cur 节点给先弄出来 ListNode cur = head.next; head.next = null; //3. 进行循环头插 while (cur != null) { ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head;}
}
寻找中间节点
876. 链表的中间结点 - 力扣(LeetCode)
思路解透
解法 1:定义一个 cur
节点,从 head
节点的地方,向后走 size()/2
步,就到了中间位置
解法 2:定义一个 slow
节点,一次走一步,在定义一个 fast
节点,一次走两步,当 fast
走完的时候,slow
就刚好在中间位置(快慢指针)
- 当有偶数个节点时,循环判断条件为:
fast != null
- 当有奇数个节点时,循环判断条件为:
fast.next != null
- 这里的两个条件判断顺序不能换,否则会报空指针异常错误
快慢指针原理:
路程一样的情况下,速度是两倍,那么当走完的时候,路程也是两倍
代码解析(法 1)
public ListNode middleNode(){ int count = 0; ListNode node = head; while(node != null){ count++; node = node.next; } ListNode cur = head; for (int i = 0; i < count/2; i++) { cur = cur.next; } return cur;
}
代码解析(法 2)
public ListNode middleNode(){ ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ //slow走一步,fast走两步slow = slow.next; fast = fast.next.next; } return slow;
}
返回链表中倒数第 k 个节点
面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)
思路解透
- 首先判断 k 是否合法,链表是否为为 null
k <= 0
,返回-1
- (下面的第二点看完再回来)因为如果
k
大于链表长度的话,当fast
走k - 1
步的时候就会走出链表,所以在fast
走k-1
步的过程中如果出现fast == null
,则返回-1
- 定义两个节点,
fast
先走k - 1
步,随后fast
和slow
一起走,当fast
走到最后了,slow
所在的地方就是倒数第k
个节点
代码解析
public int kthToLast(int k) { //判断k是否合法,链表是否为nullif(k <= 0 || head == null) { return -1; } ListNode fast = head; ListNode slow = head; int count = 0; while (count != k - 1) { //fast先向后走k-1步 fast = fast.next; if(fast == null){//判断k是否合法return -1; }count++; } while (fast.next != null){//两个节点一起向后走,直到fast走到最后一个 fast = fast.next; slow = slow.next; } return slow.val;
}
合并两个有序链表
21. 合并两个有序链表 - 力扣(LeetCode)
思路解透
创建一个新的链表,为虚拟节点(傀儡节点),然后对需要合并的两个链表中的值进行比较,谁小谁就接在虚拟节点后面
- 创建一个新的节点
newH
,在这个链表上进行合并,再创建一个tmp
节点,用来指向newH
链表中的最后一个节点 - 当
headA != null && headB != null
的时候,进行比较- 若
headA. val < headB. val
,则将headA
这个节点接在newH
后面,即接在tmp
节点后面,最后tmp
和headB
节点均向后移一位 - 若
headA. val > headB. val
,则将headB
这个节点接在newH
后面,即接在tmp
节点后面,最后tmp
和headB
节点均向后移一位
- 若
- 当
headA == null || headB == null
的时候,剩下的一个链表里面的节点直接接到newH
后面就行了 - 最后返回
newH. next
,因为newH
是一个虚拟节点,不存在于要合并的链表中,它只是一个引子
代码解析
public ListNode mergeTwoLists(ListNode headA, ListNode headB) { ListNode newH = new ListNode(0); ListNode tmp = newH; while(headA != null && headB != null){ if(headA.val < headB.val){ //将headA接到newH上面,随后后移tmp.next = headA; headA = headA.next; tmp = tmp.next; }else if{ //将headB接到newH上面,随后后移tmp.next = headB; headB = headB.next; tmp = tmp.next; } } if(headA == null){ //headA空了,将headB直接接到newH后面tmp.next = headB; } //headB空了,将headA直接接到newH后面if (headB == null) { tmp.next = headA; } return newH.next;
}
分割链表
链表分割_牛客题霸_牛客网 (nowcoder.com)
思路解透
构建两个区间,一个里面接上小于 x 的节点,一个里面接上大于 x 的节点,最后将这两个区间连接起来
- 若链表为空
- 遍历链表
- 创建一个
cur
节点,用来遍历链表
- 创建一个
- 把对应的节点放到指定区间
- 在小区间里
- 创建
bs
(before start) 节点指向区间里面最前面的一个节点,创建be
(before end) 节点指向区间里面最后一个节点 - 在小区间里面插入第一个节点的时候,
bs
和be
都指向这个节点,随后cur
向后移 - 之后插入的节点均为尾插,
bs
位置不变,be
始终指向新插入的节点
- 创建
- 在大区间里
- 创建
as
(after start) 节点指向区间里面最前面的一个节点,创建ae
(after end) 节点指向区间里面最后一个节点 - 在小区间里面插入第一个节点的时候,
as
和ae
都指向这个节点,随后cur
向后移 - 之后插入的节点均为尾插,
as
位置不变,ae
始终指向新插入的节点
- 创建
- 在小区间里
- 把两个区间连接起来
- 将
be
节点和as
节点连接起来,并且将ae
节点的next
置为null
,作为新链表的尾巴,并且返回bs
节点 - 若所有节点全在小区间里,就将
be
节点的next
置为null
,作为新链表的尾巴,并且返回bs
节点 - 若全在大区间里,则返回
ae
节点
- 将
代码解析
public ListNode partition(ListNode pHead, int x) { //判断空链表if(pHead == null){ return null; } //小区间的两个节点ListNode bs = null; ListNode be = null; //大区间的两个节点ListNode as = null; ListNode ae = null; //遍历链表的节点ListNode cur = pHead; while(cur != null){ //插入小区间if(cur.val < x){ //第一次插入if(bs == null){ bs = be = cur; }else{ be.next = cur; be = be.next; } //插入大区间 }else{ //第一次插入if(as == null){ as = ae = cur; }else{ ae.next = cur; ae = ae.next; } } cur = cur.next; } //当节点全部都在小区间时,直接返回大区间if(bs == null){ return as; } //进行大小区间的拼接be.next = as; //大区间不为空,把最后一个节点置空,作为尾巴if(as != null){ ae.next = null; } return bs;
}
回文链表
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
思路解透
- 首先用快慢指针找到中间的节点(上面第二题有讲解)
- 再对后半部分进行反转(上面第一题有讲解)
- 最后让首尾两个节点往中间走,直到相遇,返回
true
;若是偶数个节点,则只需要前面节点的next
与后面节点的值相等即可返回true
代码解析
public boolean chkPalindrome(ListNode head) { // write code here if (head == null) { return true; } //1. 找到链表的中间节点 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } //2. 反转后半节点 ListNode cur = slow.next; slow.next = null; while (cur != null) { ListNode curN = cur.next; cur.next = slow; slow = cur; cur = curN; } //3. slow从后往前,head从前往后,直到相遇 while (head != slow) { if (head.val != slow.val) { return false; } //当节点个数为偶数if (head.next == slow) return true; head = head.next; slow = slow.next; } return true;
}
相交链表
160. 相交链表 - 力扣(LeetCode)
思路解透
- 首先计算两个链表的长度,并计算他们的差值
- 随后让长的链表的头节点先走“差值“步,让他们站在同一起跑线
- 最后让他们携手同行,直到相遇,返回任意一个链表;若最终零个引用都为空,证明不相交,返回
null
代码解析
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //1. 计算两个链表的长度,并计算差值 int lenA = 0; int lenB = 0; ListNode curA = headA; ListNode curB = headB; while (curA != null) { curA = curA.next; lenA++; } while (curB != null) { curB = curB.next; lenB++; } int len = lenA - lenB; curA = headA; curB = headB; //2. 根据差值,长的链表头节点先走len步, // 让两个链表在同一起跑线 if (len > 0) { int count = 0; while (count != len) { curA = curA.next; count++; } } else { int count = 0; while (count != -len) { curB = curB.next; count++; } } //3. 两个链表的节点携手同行,直到相等 while (curA != curB) { curA = curA.next; curB = curB.next; } if (curA == null) { //若两个引用都为空,证明不相交 return null; } return curA;
}
环形链表
141. 环形链表 - 力扣(LeetCode)
思路解透
- 定义两个节点,一个一次走一步,一个一次走两步
- 当走得快的节点不为空,并且走得快的节点的 next 不为空,循环就一直继续
- 当两个节点相等,则返回
true
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况
因此:在慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
代码解析
public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) return true; } return false;
}
环形链表Ⅱ
142. 环形链表 II - 力扣(LeetCode)
思路解透
代码解析
public ListNode detectCycle(ListNode head) { //1. 判断是否有环 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; //有环,跳出循环 if (fast == slow) { break; } } //若是因为没有环而跳出循环的话,返回null if (fast == null || fast.next == null) { return null; } //此时slow在相遇点,将fast拿到起始点 //让他们相向而行,相遇点即为入口点 fast = head; while(fast != slow) { fast = fast.next; slow = slow.next; } return fast;
}