leetcode139: 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。
示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Queue<Integer> que=new LinkedList<>(); que.add(0); int[] visited = new int[s.length()]; while(!que.isEmpty()){ int start=que.remove(); if(visited[start]==0){ for(int end=start+1;end<=s.length();end++){ if(wordDict.contains(s.substring(start,end))){ if(end==s.length()){ return true; } que.add(end); } } visited[start]=1; } } return false; } }注意递归返回值为boolean的程序 找是否能够成功(找到一种就返回true，没找到就返回true[写在for循环外]) 利用 for(){ if(getValue(head,inde,str)){return true;} } return false;
leetcode142: 环入口地址 解析： 1：假设链表环外长度F，环内长度C 2：slow节点走了长度F，fast节点走了2F，此时在环内的h=Fmod C点 3：再走C-h步两者相遇，slow=(C-h)mod C fast=(2C-2h+h)mod C=(2C-h)modC=(C-h)mod C 4：此时新设指针prt，让fast和pr同时前进，走F步两者在入口处相遇。fasto=(C-FmodC+F)modC=0
public class Solution { private ListNode getIntersect(ListNode head) { ListNode tortoise = head; ListNode hare = head; while (hare != null && hare.next != null) { tortoise = tortoise.next; hare = hare.next.next; if (tortoise == hare) { return tortoise; } } return null; } public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode intersect = getIntersect(head); if (intersect == null) { return null; } ListNode ptr1 = head; ListNode ptr2 = intersect; while (ptr1 != ptr2) { ptr1 = ptr1.next; ptr2 = ptr2.next; } return ptr1; } }Leetcode 143 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1: 给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2: 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. 1：找到中点，利用快慢指针 2：翻转链表 3：交替插入
class Solution { public void reorderList(ListNode head) { if(head==null)return ; ListNode fast=head.next; ListNode slow=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; } ListNode right=reverse(slow.next); slow.next=null; ListNode left=head; while(right!=null){ ListNode next = right.next; right.next = left.next; left.next = right; right = next; left = left.next.next; } } public ListNode reverse(ListNode head){ ListNode pre=null; if(head==null)return null; while(head!=null){ ListNode tmp=head.next; head.next=pre; pre=head; head=tmp; } return pre; } }leetcode138 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 示例： 输入： {“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","next":{"id”:“2”,“next”:null,“random”:{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"2"}̲,"val":2},"rand…ref”:“2”},“val”:1} 解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
public class Solution { public Node copyRandomList(Node head) { if (head == null)return null; Node ptr = head; while (ptr != null) { Node newNode = new Node(ptr.val); newNode.next = ptr.next; ptr.next = newNode; ptr = newNode.next; } ptr = head; while (ptr != null) { ptr.next.random = (ptr.random != null) ? ptr.random.next : null; ptr = ptr.next.next; } Node ptr_old_list = head; Node ptr_new_list = head.next; Node head_old = head.next; while (ptr_old_list != null) { ptr_old_list.next = ptr_old_list.next.next; ptr_new_list.next = (ptr_new_list.next != null) ? ptr_new_list.next.next : null; ptr_old_list = ptr_old_list.next; ptr_new_list = ptr_new_list.next; } return head_old; } }