Java 链表
明天一定. 人气:0题目一
链表题——链表合并
根据给定的两个升序链表合并为一个新的升序链表
具体题目如下
解法
/** * 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; } }
加载全部内容