最近在重新學習數據結構和算法的知識，數據結構和算法問題本身比較枯燥和乏味，而且比較難不容易掌握，但是屬于程序員內功的一部分，學習起來容易上癮。

1. 單鏈表定義

package algorithm.datastructors;/*** 單向鏈表* @author i324779*/ public class ListNode {private int data;private ListNode next;public ListNode(int data) {this.data = data;}public int getData() {return data;}public void setData(int data) {this.data = data;}public ListNode getNext() {return next;}public void setNext(ListNode next) {this.next = next;} }

2, 單鏈表的一些常見操作

package algorithm.datastructors;import java.util.Stack;/*** 單鏈表的一些操作** @author i324779*/ public class ListNodeOperation {/*** 找到鏈表的中間節點* 使用兩個指針。讓第一個指針的移動速度是另一個的兩倍。* 當第一個指針到達表尾時，另一個指針則指向中間節點。* Note：如果鏈表節點數為奇數，則第（n/2）個節點為中間節點。** @param head* @return*/ListNode findMiddle(ListNode head) {ListNode ptr1x, ptr2x;ptr1x = head;ptr2x = head;int i = 0;// 不斷循環，直至達到表尾（next后繼指針為null，就表示達到最后一個節點）while (ptr1x.getNext() != null) {if (i == 0) {ptr1x = ptr1x.getNext();i = 1;} else {// 兩個指針都后移ptr1x = ptr1x.getNext();ptr2x = ptr2x.getNext();i = 0;}}return ptr2x;}/*** 從表尾開始輸出鏈表。** @param head*/void printListFromEnd(ListNode head) {if (head == null) {return;}printListFromEnd(head.getNext());System.out.println(head.getData());}/*** 檢查鏈表的長度是奇數還是偶數。* 使用一個在鏈表中每次向后移動兩個節點的指針。* 最后，如果指針值為null，那么聊表長度為偶數；* 否則指針指向表尾節點，鏈表長度為奇數。** @param head* @return*/public int isLinkedListLengthEven(ListNode head) {while (head != null && head.getNext() != null) {head = head.getNext().getNext();}if (head == null) {return 0;} else {return 1;}}/*** 合并兩個有序鏈表為一個新的有序鏈表。** @param node1* @param node2* @return*/public ListNode mergeList(ListNode node1, ListNode node2) {if (node1 == null) {return node2;}if (node2 == null) {return node1;}ListNode result;if (node1.getData() <= node2.getData()) {result = node1;result.setNext(mergeList(node1.getNext(), node2));} else {result = node2;result.setNext(mergeList(node2.getNext(), node1));}return result;}/*** 逆置單向鏈表。** @param head 表頭* @return 逆置后的單向鏈表。*/ListNode reverseList(ListNode head) {ListNode temp = null;ListNode nextNode;while (head != null) {nextNode = head.getNext();head.setNext(temp);temp = head;head = nextNode;}return temp;}/*** 找到鏈表的倒數第n個結點* 使用一次鏈表掃描解決問題。* 使用兩個指針pNthNode和pTemp。* 首先，兩個指針都指向鏈表的頭結點。僅當pTemp（沿著鏈表）進行了n次移動后，* pNthNode才開始移動。然后兩個指針同時移動直至tTemp到達表尾。* 這時pNthNode指針所指的結點就是所求的結點，也就是鏈表的倒數第n個結點。** @param head* @param nthNode* @return*/ListNode nthNodeFromEnd(ListNode head, int nthNode) {ListNode pTemp = head;ListNode pNnthNode = null;for (int count = 1; count < nthNode; count++) {if (pTemp != null) {pTemp = pTemp.getNext();}}while (pTemp != null) {if (pNnthNode == null) {pNnthNode = head;} else {pNnthNode = pNnthNode.getNext();}pTemp = pTemp.getNext();}return pNnthNode;}/*** 給定兩個有序單鏈表的頭指針head1 和head2， 打印兩個鏈表的公共部分。** @param head1 有序鏈表1* @param head2 有序鏈表2*/public void printCommonPart(ListNode head1, ListNode head2) {if (head1 == null || head2 == null) {System.out.println("Node is null");return;}System.out.println("Common Part: ");while (head1 != null && head2 != null) {if (head1.getData() < head2.getData()) {head1 = head1.getNext();} else if (head1.getData() > head2.getData()) {head2 = head2.getNext();} else {System.out.println(head1.getData());head1 = head1.getNext();head2 = head2.getNext();}}}/*** 判斷是否有環** @param head 鏈表頭結點* @return 是否有環*/public static boolean isCycle(ListNode head) {ListNode p1 = head;ListNode p2 = head;while (p2 != null && p2.getNext() != null) {p1 = p1.getNext();p2 = p2.getNext().getNext();if (p1 == p2) {return true;}}return false;}/*** 逐對逆置鏈表** @param head* @return*/private void reversePairRecursive(ListNode head) {if (head == null || head.getNext() == null) {return;}ListNode cur = head.getNext();ListNode pre = head;ListNode next;while (cur != null && cur.getNext() != null) {next = cur.getNext().getNext();pre.setNext(cur.getNext());cur.getNext().setNext(cur);cur.setNext(next);pre = cur;cur = next;}}/*** 判斷一個鏈表是否為回文結構** @param head 單鏈表的頭結點* @return true：回文結構；false：不是回文結構*/public boolean isPalindrome(ListNode head) {Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.getNext();}while (head != null) {if (head.getData() != stack.pop().getData()) {return false;}head = head.getNext();}return true;}public static void main(String[] args) {ListNodeOperation operation = new ListNodeOperation();int i = 1;ListNode head = new ListNode();head.setNext(null);ListNode tmp;ListNode cur = head;for (; i < 8; i++) {tmp = new ListNode();tmp.setData(i);tmp.setNext(null);cur.setNext(tmp);cur = tmp;}System.out.println("順序輸出：");for (cur = head.getNext(); cur != null; cur = cur.getNext()) {System.out.print(cur.getData() + " ");}operation.reversePairRecursive(head);System.out.println("\n逆序輸出：");for (cur = head.getNext(); cur != null; cur = cur.getNext()) {System.out.print(cur.getData() + " ");}} }

轉載于:https://www.cnblogs.com/IcanFixIt/p/10471386.html

總結

以上是生活随笔為你收集整理的单链表常见操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。