算法入門篇五 鏈表

牛客網 算法入門篇

判斷一個鏈表是否為回文結構

  • 給定一個單鏈表的頭節點head，請判斷這個鏈表是否為回文結構
  • 1->2->1，返回為True;1->2->3為False

思路：

  • 1，遍歷鏈表，將所有元素壓入棧中，然后再次從頭遍歷，和棧中取出的元素比較。如果所有元素都是一致的化，說明是屬于回文結構的。
  • 2，不是將所有的元素都入棧，只是將一般的元素壓入棧中，引出新的問題，如何確認鏈表的中點？設計快指針和慢指針，快指針每次移動2步，慢指針每次移動1步，當快指針移動到末尾，慢指針所指向的位置就是鏈表的中點位置。但是，鏈表長度需要分奇數和偶數。（節約空間）
  • 3，不需要使用棧，僅僅使用有限幾個變量。和方法2一致，使用快慢指針找到鏈表的中點，將鏈表中點之后的元素逆序，然后逐一比較，但是需要注意的是，最后需要將鏈表變回原先的樣子。

代碼：

package class04;import java.util.Stack;public class Code04_IsPalindromeList {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}// need n extra spacepublic static boolean isPalindrome1(Node head) {Stack<Node> stack = new Stack<Node>();Node cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}while (head != null) {if (head.value != stack.pop().value) {return false;}head = head.next;}return true;}// need n/2 extra spacepublic static boolean isPalindrome2(Node head) {if (head == null || head.next == null) {return true;}Node right = head.next;Node cur = head;while (cur.next != null && cur.next.next != null) {right = right.next;cur = cur.next.next;}Stack<Node> stack = new Stack<Node>();while (right != null) {stack.push(right);right = right.next;}while (!stack.isEmpty()) {if (head.value != stack.pop().value) {return false;}head = head.next;}return true;}// need O(1) extra spacepublic static boolean isPalindrome3(Node head) {if (head == null || head.next == null) {return true;}Node n1 = head;Node n2 = head;while (n2.next != null && n2.next.next != null) { // find mid noden1 = n1.next; // n1 -> midn2 = n2.next.next; // n2 -> end}n2 = n1.next; // n2 -> right part first noden1.next = null; // mid.next -> nullNode n3 = null;while (n2 != null) { // right part convertn3 = n2.next; // n3 -> save next noden2.next = n1; // next of right node convertn1 = n2; // n1 moven2 = n3; // n2 move}n3 = n1; // n3 -> save last noden2 = head;// n2 -> left first nodeboolean res = true;while (n1 != null && n2 != null) { // check palindromeif (n1.value != n2.value) {res = false;break;}n1 = n1.next; // left to midn2 = n2.next; // right to mid}n1 = n3.next;n3.next = null;while (n1 != null) { // recover listn2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}public static void printLinkedList(Node node) {System.out.print("Linked List: ");while (node != null) {System.out.print(node.value + " ");node = node.next;}System.out.println();}public static void main(String[] args) {Node head = null;printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(2);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(2);head.next.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");}}

將單鏈表按照給定的數值，劃分成左邊小、中間相等、右邊大的形式

思路

  • 1，申請一個鏈表長度大小一致的數組，然后遍歷鏈表的過程中，將每一個點放到數組容器中，在數組里面進行荷蘭國旗問題，再把數組容器中的元素都串聯起來，形成一個鏈表返回

  • 2，保證穩定性：根據題目要求設置三個區，小于區、等于區和大于區，每個區間包含兩個變量，開始節點和結尾節點，一共設置6個變量，6個變量都指向null；當遇到第一個元素3的時候，它是小于指定元素5的，將小于區域的開始和結束指針都指向3；第二個元素是5，屬于等于區，讓等于區的start和end都指向第二個元素5；第3個元素也是5，讓等于區的end只想第三個元素。以此類推，得到上面的結果。最后將小于區域的end指針鏈接等于區域的start指針，等于區域的end指針鏈接大于區域的start指針。需要注意的是，有可能上面6個變量有不存在的情形，需要仔細判別。

兩個單鏈表相交的一系列問題

  • 給定兩個可能有環也可能無環的單鏈表，頭節點head1和head2，實現一個函數，如果兩個鏈表相交，返回相交的第一個節點，如果不相交，返回null
  • 兩個鏈表的長度之和為N，時間復雜度為O（N），額外空間復雜度為O（1）
  • 相交：共用內存地址??
  • 有環/無環：寫一個函數，輸入的類型是鏈表的頭節點，判斷是否有環，以及返回第一個有環的節點。使用集合來做，遍歷鏈表，每遍歷一個元素，將其放入到集合中，判定是否存在此元素，如果將一個元素放入集合中，發現他已經存在，則是有環的，并且他就是第一個入環節點。

  • 使用快慢指針來做，快指針每次移動倆個位置，慢指針每次移動一個位置，當快慢指針第一次相交之后，快指針回到鏈表的起始點，慢指針呆在原地不動。然后快指針和慢指針都每次移動一個位置，當他們再次相遇之后，相遇的元素就是入環的第一個元素，且能證明這個鏈表是有環的結構。上圖所示的是環外4個點，環內4個點，可以按照這個流程走一遍。
  • 兩個無環鏈表相交問題，哪個鏈表長，先走比短鏈表多余的部分，然后一起走，只要有一點的內存地址相穩合，則代表兩者相交。
  • 如果一個是有環的，一個是無環的，那么他倆一定不相交

  • 如果兩者都是環狀結構，那么可以劃分為上面三種形式。1，兩者都是環，都不相交；2，兩者共用環，卻已經在環外相交，入環點一樣；3，共用環，但是接入環的點不一樣。
  • 第一種情形，如上圖的左邊的圖形“6”，loop1為相交點，讓loop1順著next指針走一圈，如果走了一圈沒有遇到loop2，則二者不相交。
  • 第二種類型，只需要判斷二者的入環節點是否一致，就可以判定是否相交。如果需要判斷相交的第一個節點，入環點作為終止節點，轉化為先前的長短鏈，找相交點。
  • 第一種情形，如上圖的右邊的圖形所示，loop1為左邊的相交點，loop2為右邊的相交點，讓loop1順著next指針走一圈，如果走了一圈遇到loop2，則二者相交。loop1 和loop2都是相交節點，只不過loop1距離鏈表1更近，loop2距離鏈表2更近。
package class04;public class Code07_FindFirstIntersectNode {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node getIntersectNode(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node loop1 = getLoopNode(head1);Node loop2 = getLoopNode(head2);if (loop1 == null && loop2 == null) {return noLoop(head1, head2);}if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);}return null;}// 找到鏈表第一個入環節點，如果無環，返回nullpublic static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node n1 = head.next; // n1 -> slowNode n2 = head.next.next; // n2 -> fastwhile (n1 != n2) {if (n2.next == null || n2.next.next == null) {return null;}n2 = n2.next.next;n1 = n1.next;}n2 = head; // n2 -> walk again from headwhile (n1 != n2) {n1 = n1.next;n2 = n2.next;}return n1;}// 如果兩個鏈表都無環，返回第一個相交節點，如果不想交，返回nullpublic static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}// n? :? 鏈表1長度減去鏈表2長度的值cur1 = n > 0 ? head1 : head2; // 誰長，誰的頭變成cur1cur2 = cur1 == head1 ? head2 : head1; // 誰短，誰的頭變成cur2n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}// 兩個有環鏈表，返回第一個相交節點，如果不想交返回nullpublic static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;}cur1 = cur1.next;}return null;}}public static void main(String[] args) {// 1->2->3->4->5->6->7->nullNode head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(6);head1.next.next.next.next.next.next = new Node(7);// 0->9->8->6->7->nullNode head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next.next.next.next.next; // 8->6System.out.println(getIntersectNode(head1, head2).value);// 1->2->3->4->5->6->7->4...head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(6);head1.next.next.next.next.next.next = new Node(7);head1.next.next.next.next.next.next = head1.next.next.next; // 7->4// 0->9->8->2...head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next; // 8->2System.out.println(getIntersectNode(head1, head2).value);// 0->9->8->6->4->5->6..head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next.next.next.next.next; // 8->6System.out.println(getIntersectNode(head1, head2).value);}}

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/447215.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/447215.shtml
英文地址，請注明出處：http://en.pswp.cn/news/447215.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

實時流媒體編程基于Linux環境開發

實時流媒體編程基于Linux環境開發

一、流媒體簡介 隨著Internet的日益普及&#xff0c;在網絡上傳輸的數據已經不再局限于文字和圖形&#xff0c;而是逐漸向聲音和視頻等多媒體格式過渡。目前在網絡上傳輸音頻/視頻&#xff08;Audio/Video&#xff0c;簡稱A/V&#xff09;等多媒體文件時&#xff0c;基本上只有…
閱讀更多...
算法入門篇六 二叉樹

算法入門篇六 二叉樹

牛客網 算法入門篇 左程云老師 個人復習&#xff0c;如果侵全&#xff0c;設為私密 二叉樹遍歷&#xff08;遞歸&#xff09; 先序遍歷&#xff08;中&#xff0c;左&#xff0c;右&#xff09; 中序遍歷&#xff08;左&#xff0c;中&#xff0c;右&#xff09; 后序遍歷&a…
閱讀更多...
VLC詳細的使用說明以及配置說明綜合示范實例精通VLC開發

VLC詳細的使用說明以及配置說明綜合示范實例精通VLC開發

vlc的全名是Video LanClient&#xff0c;是一個開源的、跨平臺的視頻播放器。VLC支持大量的音視頻傳輸、封裝和編碼格式&#xff0c;完整的功能特性列表可以在這里獲得http://www.videolan.org/vlc/features.html&#xff0c;下面給出一個簡要的不完整的列表&#xff1a;操作系…
閱讀更多...
算法入門篇七 前綴樹

算法入門篇七 前綴樹

牛客網 左程云老師的算法入門課 找二叉樹的節點的后繼節點 原則 如果節點有右子樹&#xff0c;那么后繼節點就是右子樹的最左邊的第一個節點如果節點沒有右子樹&#xff0c;如果節點是父節點的右孩子&#xff0c;就繼續往上找&#xff0c;直到找到一個父節點是沿途節點的父節…
閱讀更多...
VLC視頻播放器原理詳細分析含TS流格式分析

VLC視頻播放器原理詳細分析含TS流格式分析

vlc是一個功能強大的玩意&#xff0c;能做很多有意思的事情。最簡單的&#xff0c;從界面打開一個文件播放&#xff0c;也可以在命令行下使用&#xff0c;如C:\Program Files\VideoLAN\VLC>vlc.exe test.ts獲取內置的幫助&#xff0c;會寫到vlc-help.txtC:\Program Files\Vi…
閱讀更多...
算法入門篇八 貪心算法

算法入門篇八 貪心算法

牛客網 左程云老師的算法入門課 貪心算法 貪心算法的解題步驟 例子 題目要求 解題策略 按照結束時間早的會議先安排&#xff0c;比如先安排【2&#xff0c;4】&#xff0c;當4結束了&#xff0c;所有開始時間小于4的全部淘汰&#xff0c;【1&#xff0c;7】、【3&#xff…
閱讀更多...
算法入門篇九 暴力遞歸

算法入門篇九 暴力遞歸

牛客網 左程云老師的算法入門課 暴力遞歸 原則 漢諾塔問題 問題 打印n層漢諾塔從左邊移動到最右邊的過程 思想 一共六個過程&#xff0c;左到右、左到中&#xff0c;中到左&#xff0c;中到右&#xff0c;右到左&#xff0c;右到中&#xff0c;互相嵌套使用 左到右 將1…
閱讀更多...
rtsp和sdp

rtsp和sdp

RTSP 是由Realnetwork 和Netscape共同提出的如何有效地在IP網絡上傳輸流媒體數據的應用層協議 。 實時流協議&#xff08;RTSP&#xff09;建立并控制一個或幾個時間同步的連續流媒體&#xff0c;如音頻和視頻。盡管連續媒體流與控制流交叉是可能的&#xff0c;RTSP本身并不發…
閱讀更多...
使用javascript實現對于chineseocr的API調用

使用javascript實現對于chineseocr的API調用

ChineseOCR在線API 網頁地址 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Javascript工具 在線工具網頁鏈接在線Base64 轉化工具 在線工具…
閱讀更多...
移動流媒體業務的技術與標準

移動流媒體業務的技術與標準

1 引言 　　流媒體業務是從Internet上發展起來的一種多媒體應用&#xff0c;指使用流&#xff08;Streaming&#xff09;方式在網絡上傳輸的多媒體文件&#xff0c;包括音頻、視頻和動畫等。 　　流媒體傳輸技術的主要特點是以流&#xff08;streaming&#xff09;的形式進行多…
閱讀更多...
使用python實現對于chineseocr的API調用

使用python實現對于chineseocr的API調用

ChineseOCR在線API 網頁鏈接 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Base64 轉化工具 Base64在線小工具代碼修改 新增一個變量fill_w…
閱讀更多...
UDP穿透NAT

UDP穿透NAT

NAT(Network AddressTranslators)&#xff0c;網絡地址轉換&#xff1a; 網絡地址轉換是在IP地址日益缺乏的情況下產生的&#xff0c;它的主要目的就是為了能夠地址重用。NAT分為兩大類&#xff0c;基本的NAT和NAPT(Network Address/Port Translator)。 最開始NAT是運行在路由器…
閱讀更多...
算法入門篇十 圖

算法入門篇十 圖

圖的存儲方式 臨接表臨接矩陣 表達 點集/邊集有向圖/無向圖 Graph&#xff08;大結構就是圖&#xff09;&#xff08;包含點集合和邊集合&#xff09; import java.util.HashMap; import java.util.HashSet;public class Graph {public HashMap<Integer, Node> nodes;…
閱讀更多...
SDP協議 學習筆記

SDP協議 學習筆記

SDP:Session Description ProtocolSDP格式:Session descriptionv (protocolversion)o (owner/creatorand session identifier)s (sessionname)i* (sessioninformation)u* (URI ofdescription)e* (emailaddress)p* (phonenumber)c*(connection information - not required if in…
閱讀更多...
以太坊私有鏈 使用dev模式

以太坊私有鏈 使用dev模式

dev 使用dev模式&#xff0c;創建一個管理員賬號&#xff0c;控制挖礦&#xff0c;將證明機制改為POA啟動dev模式&#xff0c;需要重新創建一個文件夾&#xff0c;重新搭建私有鏈條 命令 mkdir myDevChain cd myDevChain geth --datadir . --dev console 2>output.log 實…
閱讀更多...
超文本傳輸協議

超文本傳輸協議

超文本傳輸協議 超文本傳輸協議超文件傳輸協定(HTTP&#xff0c;HyperTextTransfer Protocol)是因特網上應用最為廣泛的一種網絡傳輸協定。所有的WWW文件都必須遵守這個標準。設計HTTP最初的目的是為了提供一種發布和接收HTML頁面的方法。 目錄 介紹請求信息請求方法安全方法超…
閱讀更多...
以太坊區塊鏈 JSON-RPC

以太坊區塊鏈 JSON-RPC

RPC定義 以太坊客戶端提供了API和一組遠程調用的&#xff08;RPC&#xff09;命令&#xff0c;這些命令被編碼成json的格式&#xff0c;被叫做JSON-RPC-API。本質上&#xff0c;JSON-RPC API就是一個接口&#xff0c;允許我們編寫的程序使用以太坊客戶端作為網關&#xff0c;訪…
閱讀更多...
利用MFC調用libvlc.dll作一個簡單的播放器

利用MFC調用libvlc.dll作一個簡單的播放器

簡單介紹MFC調用libvlc.dll作一個簡單的播放器&#xff0c;拋磚引玉&#xff0c;各位VC達人繼續深入研究&#xff0c;Jeremiah對VC確實不太感興趣&#xff0c;所以就不做太深入的研究了。2009.10.29修改&#xff1a;加入clip_children屬性設置。參開第1步。環境&#xff1a; …
閱讀更多...
對于以太坊虛擬機 （EVM）及其相關知識的講解

對于以太坊虛擬機 （EVM）及其相關知識的講解

以太坊虛擬機&#xff08;EVM&#xff09; EVM是智能合約的運行環境作為區塊驗證協議的一部分&#xff0c;參與網絡的每個節點都會運行EVM&#xff0c;審查節點會檢查驗證正在驗證的區塊中列出的交易&#xff0c;并運行EVM中交易觸發的代碼EVM是沙盒封裝的&#xff0c;并且是完…
閱讀更多...
對于以太坊的Solidity語言介紹

對于以太坊的Solidity語言介紹

Solidity是什么 Solidity是一門面向合約的、為實現智能合約而創建的高級編程語言&#xff0c;主要目的是為了在以太坊虛擬機&#xff08;EVM&#xff09;上運行Solidity是靜態語言&#xff0c;支持繼承、庫和復雜的用戶定義等特性內含的類型除了常見的編程語言中的標準類型&am…
閱讀更多...
最新文章

Copyright @ 2022~2023