-
反轉一個單鏈表，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
/** * Definition for singly-linked list. */ class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } /** * 反轉鏈表 * 1. 遍歷鏈表, 使用集合保存資料元素, 新宣告一個鏈表, 遍歷集合復制 時間復雜度是O(n) * 2. 宣告兩個鏈表, 直接反轉(有種陣列中兩個元素交換的感覺) * <p> * 輸入: 1->2->3->4->5->NULL * 輸出: 5->4->3->2->1->NULL * <p/> * 執行用時 :0 ms, 在所有 java 提交中擊敗了100.00%的用戶 * 記憶體消耗 :37 MB, 在所有 java 提交中擊敗了45.52%的用戶 * @param head 鏈表頭 * @return */ public static ListNode reverseList(ListNode head) { if(head == null) { return null; } ListNode cur = head, pre = null, temp = null; while(cur != null) { temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } /** * 執行用時 :3 ms, 在所有 java 提交中擊敗了 7.38%的用戶 * 記憶體消耗 :36.8 MB, 在所有 java 提交中擊敗了50.79% 的用戶 * @param head * @return */ public static ListNode reverseList1(ListNode head) { if(head == null) { return null; } List<Integer> list = new ArrayList<>(); while(head != null) { list.add(0,head.val); head = head.next; } ListNode result = new ListNode(list.get(0)); ListNode temp = result; for (int i = 1; i < list.size(); i++) { ListNode node = new ListNode(list.get(i)); result.next = node; result = node; } return temp; } // 測驗 ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = null; ListNode node = reverseList(node1); while (node != null) { System.out.println(node.val); node = node.next; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138116.html
標籤：其他
上一篇：用js刷劍指offer(從1到n整數中1出現的次數)
下一篇：一些常用的語音特征提取演算法