剑指Offer之Java算法习题精讲链表专项训练

剑指Offer之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 set = new HashSet();

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 set = new HashSet();

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 {

TCjsNVeeAy 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 set = new HashSet();

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

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;

}

}

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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。