剑指Offer之Java算法习题精讲链表专项训练
时间：2022-11-30 10:58:51 | 栏目：JAVA代码 | 点击：次
题目一
链表题——链表合并
根据给定的两个升序链表合并为一个新的升序链表
具体题目如下
解法
/**
* 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 mergeTwoLists(ListNode list1, ListNode list2) {
ListNode a = new ListNode(0),b = a;
while(list1!=null&&list2!=null){
if(list1.val<=list2.val){
a.next = list1;
list1 = list1.next;
}else{
a.next = list2;
list2 = list2.next;
}
a = a.next;
}
if(list1==null){
a.next = list2;
}
if(list2==null){
a.next = list1;
}
return b.next;
}
}
题目二
链表题——查找链表
根据给定的链表头文件判断其中是否有环
具体题目如下
解法一
/**
* 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) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(!set.add(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
解法二
/**
* 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){
if(fast.next==null) return false;
slow = slow.next;
fast = fast.next.next;
if(fast==slow) return true;
}
return false;
}
}
题目三
链表题——查找数组中元素位置
根据给定的链表头节点查找返回链表入环的第一个节点
具体题目如下
解法一
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(!set.add(head)){
return head;
}
set.add(head);
head = head.next;
}
return null;
}
}
解法二
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null){
if(fast.next==null) return null;
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
slow = head;
break;
}
}
while(fast!=null){
if(slow == fast){
return slow;
}
slow = slow.next;
fast = fast.next;
}
return null;
}
}
题目四
链表题——查找链表相交起始节点
根据给定的两个链表头节点按照指定条件查找起始节点
具体题目如下
解法一
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(headA!=null){
set.add(headA);
headA = headA.next;
}
while(headB!=null){
if(!set.add(headB)){
return headB;
}
set.add(headB);
headB = headB.next;
}
return null;
}
}
解法二
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while(a != b){
if(a == null) a = headB;
else a = a.next;
if(b == null) b = headA;
else b = b.next;
}
return a;
}
}
题目五
链表题——链表操作
根据给定的链表删除指定节点并返回头节点
具体题目如下
解法
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode node = new ListNode(-1);
node.next = head;
ListNode x = findFromEnd(node,n+1);
x.next = x.next.next;
return node.next;
}
private ListNode findFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i = 0;i<k;i++){
fast = fast.next;
}
while(fast!=null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
题目六
链表题——查找链表中间节点
根据给定的链表头节点查找其中间节点
具体题目如下
解法
/**
* 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 middleNode(ListNode head) {
ListNode fast = head ;
ListNode slow = head ;
while(fast!=null){
if(fast.next == null) return slow;
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}