首页 > 代码库 > 感觉题又有些难了，生活没有那么简单
感觉题又有些难了，生活没有那么简单
（1）Remove Nth Node From End of List
解题思路：
题目要求只使用一次遍历。可以使用指针来完成单程解决方案。快速移动一个指针向前移动n + 1个位置，以保持两个指针之间的间隙，然后以相同的速度移动两个指针。
最后，当快速指针到达结束时，慢指针将在n + 1个位置后面 - 只是正确的点，以便能够跳过下一个节点。
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public ListNode removeNthFromEnd(ListNode head, int n) { 11 ListNode start = new ListNode(0); 12 ListNode fast = start, slow = start; 13 slow.next = head; 14 15 for (int i = 1; i <= n+1; i++) { 16 fast = fast.next; 17 } 18 19 while (fast != null) { 20 slow = slow.next; 21 fast = fast.next; 22 } 23 24 slow.next = slow.next.next; 25 return start.next; 26 } 27 }
(2)Linked List Cycle
解题思路：
使用快慢引用的思路。两个引用都指向链表头，从链表头开始遍历，慢引用每次前进一步，而快引用每次前进两步，如果链表是有环路的，那么快引用终将追上慢引用；如果没有环路，那么遍历就会有结束的时候
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public Boolean hasCycle(ListNode head) { 14 if (head == null) { 15 return false; 16 } 17 18 ListNode fast, slow; 19 fast = head; 20 slow = head; 21 while (fast.next != null && fast.next.next != null) { 22 slow = slow.next; 23 fast = fast.next.next; 24 if(fast == slow) { 25 return true; 26 } 27 } 28 return false; 29 } 30 }
(3)Remove Linked List Elements
解题思路：简单明了，遍历整个链表，遇到相应值得节点删掉即可。
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public ListNode removeElements(ListNode head, int val) { 11 ListNode dummy = new ListNode(0); 12 dummy.next = head; 13 head = dummy; 14 while (head.next != null) { 15 if (head.next.val == val) { 16 head.next = head.next.next; 17 } else { 18 head = head.next; 19 } 20 } 21 return dummy.next; 22 } 23 }
(4)Intersection of Two Linked Lists
解题思路：
1，获取两个列表的长度。2，将它们对齐到相同的起点。3，将它们一起移动，直到找到交点，或者结束null
代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 14 int lenA = length(headA); 15 int lenB = length(headB); 16 // move headA and headB to the same start point 17 while (lenA > lenB) { 18 headA = headA.next; 19 lenA--; 20 } 21 while (lenA < lenB) { 22 headB = headB.next; 23 lenB--; 24 } 25 // find the intersection until end 26 while (headA != headB) { 27 headA = headA.next; 28 headB = headB.next; 29 } 30 return headA; 31 32 } 33 private int length (ListNode node){ 34 int length = 0; 35 while (node != null) { 36 node = node.next; 37 length++; 38 } 39 return length; 40 } 41 }
感觉题又有些难了，生活没有那么简单
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。