dsadas

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*//** 解法一：通過(guò)set數(shù)據(jù)結(jié)構(gòu)來(lái)做 時(shí)間復(fù)雜度O(m+n) 空間復(fù)雜度O(max(m,n))如果這個(gè)題再?gòu)?fù)雜一些，就需要用map數(shù)據(jù)結(jié)構(gòu)*/ // public class Solution { // public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // Set<ListNode> set = new HashSet<>(); // ListNode tempAB = headA; // while(tempAB!=null){ // set.add(tempAB); // tempAB = tempAB.next; // } // tempAB = headB; // while(tempAB!=null){ // if(set.contains(tempAB)){ // return tempAB; // } // tempAB = tempAB.next; // } // return null; // } // }/** 解法二：雙指針，分別 tempA，tempB,讓他們分別遍歷headA,headB，當(dāng)走完各自的鏈表后，直接再走另一鏈路：即： tempA 走的 headA+headB temp 走的 headB+headA (具體可以看圖的解析)時(shí)間復(fù)雜度： O(m+n) 空間復(fù)雜度O(1)*/ // public class Solution { // public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // ListNode tempA = headA; // ListNode tempB = headB; // while(tempA != tempB){ //如果不相交，則它們同時(shí)遍歷完headA和headB，則返回的為null // tempA = tempA != null ? tempA.next : headB; // tempB = tempB != null ? tempB.next : headA; // } // return tempA; // } // }/** 解法三： 暴力解決*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tempA = headA;while(tempA != null){ ListNode tempB = headB;while(tempB != null){if(tempA == tempB){return tempA;}tempB = tempB.next;}tempA = tempA.next;}return tempA;} }

/*** 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; }* }*//**迭代： 通過(guò)兩個(gè)指針進(jìn)行迭代: 我們可以申請(qǐng)兩個(gè)指針，第一個(gè)指針叫 pre，最初是指向 null 的。 第二個(gè)指針 cur 指向 head，然后不斷遍歷 cur。 每次迭代到 cur，都將 cur 的 next 指向 pre，然后 pre 和 cur 前進(jìn)一位。 都迭代完了(cur 變成 null 了)，pre 就是最后一個(gè)節(jié)點(diǎn)了。*/ // class Solution { // public ListNode reverseList(ListNode head) { // //申請(qǐng)節(jié)點(diǎn)，pre和 cur，pre指向null // ListNode pre = null; // ListNode cur = head;// ListNode tmp = null; // while(cur!=null) { // //記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) // tmp = cur.next; // //然后將當(dāng)前節(jié)點(diǎn)指向pre // cur.next = pre; // //pre和cur節(jié)點(diǎn)都前進(jìn)一位 // pre = cur; // cur = tmp; // } // return pre; // } // }/**遞歸 遞歸先寫遞歸頭,然后遞歸體： 一定要注意 head.next.next=head，head是當(dāng)前的，(head.next是指向下一個(gè)節(jié)點(diǎn)).next=head是指回來(lái)， 也就鏈表?yè)Q個(gè)防線，然后head.next = null是為了結(jié)束遞歸用*/ class Solution {public ListNode reverseList(ListNode head) {//遞歸終止條件是當(dāng)前為空，或者下一個(gè)節(jié)點(diǎn)為空if(head==null || head.next==null) {return head;}//這里的cur就是最后一個(gè)節(jié)點(diǎn)ListNode cur = reverseList(head.next);//這里請(qǐng)配合動(dòng)畫演示理解//如果鏈表是 1->2->3->4->5，那么此時(shí)的cur就是5//而head是4，head的下一個(gè)是5，下下一個(gè)是空//所以head.next.next 就是5->4head.next.next = head;//防止鏈表循環(huán)，需要將head.next設(shè)置為空head.next = null;//每層遞歸函數(shù)都返回cur，也就是最后一個(gè)節(jié)點(diǎn)return cur;} }

總結(jié)

以上是生活随笔為你收集整理的LeetCode 热题 HOT 100 -------160. 相交链表（链表）206. 反转链表（递归、回溯）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。