反轉鏈表
206. 反轉鏈表
劍指 Offer 24. 反轉鏈表
反轉一個單鏈表，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL進階:
你可以迭代或遞回地反轉鏈表，你能否用兩種方法解決這道題？來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
這是一個基礎題了，應該能在紙上寫出來！！！
class Solution {
public ListNode reverseList(ListNode head) {
// [prev] [curr]1->2->3->4->5
// NULL<-[prev]1 [curr]2->3->4->5
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
// 保存當前節點的下一個節點
ListNode tmp = curr.next;
// 頭插法
curr.next = prev;
prev = curr;
// 鏈表向后移動一節
curr = tmp;
}
return prev;
}
}
92. 反轉鏈表 II
反轉從位置 m 到 n 的鏈表，請使用一趟掃描完成反轉，
說明:
1 ≤ m ≤ n ≤ 鏈表長度，示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
這個題和反轉鏈表 I 實際上是一樣的，只是增加了指定位置約束，
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// 哨兵節點
// [1] [sentinel]->1[head]->2->3->4->5->NULL, m = 2, n = 4
ListNode sentinel = new ListNode(0);
sentinel.next = head;
// 先將prev節點移動到第m個節點的*頭節點*，示例中`m=2,n=4`也就是 `1` 的位置，作為`m-n`區間反轉后的頭節點
// [2] [sentinel|prev]->1[head]->2->3->4->5->NULL, m = 2, n = 4
ListNode prev = sentinel;
for (int i = 1; i < m; i++) {
prev = prev.next;
}
// [3] [sentinel]->1[head|prev]->2->3->4->5->NULL, m = 2, n = 4
// 反轉第 m-n 位置的節點，即2->3->4這一段
// [4] [sentinel]->1[head|prev]->2[curr]->3->4->5->NULL, m = 2, n = 4
// {
// loop
// [5] [sentinel]->1[head|prev]->2[curr]->3[next]->4->5->NULL
// [6] [sentinel]->1[head|prev]->2[curr]->4->5->NULL
// 3[next]->4->5->NULL
// [7] [sentinel]->1[head|prev]->2[curr]->4->5->NULL
// 3[next]->2[curr]->4->5->NULL
// [8] [sentinel]->1[head|prev]->3[next]->2[curr]->4->5->NULL
// }
ListNode curr = prev.next;
for (int i = m; i < n; i++) {
ListNode next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return sentinel.next;
}
}
劍指 Offer 06. 從尾到頭列印鏈表
輸入一個鏈表的頭節點，從尾到頭反過來回傳每個節點的值（用陣列回傳），
示例 1：
輸入：head = [1,3,2]
輸出：[2,3,1]限制：
0 <= 鏈表長度 <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
class Solution {
public int[] reversePrint(ListNode head) {
// 1. 求鏈表長度
int length = 0;
ListNode cursor = head;
while (cursor != null) {
cursor = cursor.next;
length++;
}
// 2. 預分配 length 長度的陣列作為回傳值，利用陣列隨機訪問特性輸出結果
int[] array = new int[length];
for (int idx = length -1; idx >= 0; idx++) {
array[idx] = head.val;
head = head.next;
}
return array;
}
}
61. 旋轉鏈表
給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，其中 k 是非負數，
示例 1:
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉 1 步: 5->1->2->3->4->NULL
向右旋轉 2 步: 4->5->1->2->3->NULL
示例 2:輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉 1 步: 2->0->1->NULL
向右旋轉 2 步: 1->2->0->NULL
向右旋轉 3 步: 0->1->2->NULL
向右旋轉 4 步: 2->0->1->NULL來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotate-list
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
// 1. 先遍歷一遍鏈表，求鏈表長度，將鏈表轉成環形鏈表
int length = 1;
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
length++;
}
// 1.1. 現在 curr 指向了鏈表的尾節點, 將尾節點連接到頭節點, 形成回圈鏈表
curr.next = head;
// 2. 鏈表向右旋 k 個位置, 也就是向左移動 length - (k % length) 個位置
int shift = length - (k % length);
for (int i = 0; i < shift; i++) {
curr = curr.next;
}
// 2.1 此時 curr 指向了旋轉鏈表的尾節點
head = curr.next;
curr.next = null;
return head;
}
}
劍指 Offer 22. 鏈表中倒數第k個節點
輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，例如，一個鏈表有6個節點，從頭節點開始，它們的值依次是1、2、3、4、5、6，這個鏈表的倒數第3個節點是值為4的節點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.
回傳鏈表 4->5.
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
劍指 Offer 35. 復雜鏈表的復制
請實作 copyRandomList 函式，復制一個復雜鏈表，在復雜鏈表中，每個節點除了有一個 next 指標指向下一個節點，還有一個 random 指標指向鏈表中的任意節點或者 null，
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]
示例 3：輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]
示例 4：輸入：head = []
輸出：[]
解釋：給定的鏈表為空（空指標），因此回傳 null，提示：
-10000 <= Node.val <= 10000
Node.random 為空（null）或指向鏈表中的節點，
節點數目不超過 1000 ，注意：本題與主站 138 題相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
// 1->2->3->4->5->6->NULL
// 1. 復制鏈表節點
Node curr = head;
while (curr != null) {
// 復制 curr 節點
Node copy = new Node(curr.val);
// 將 copy 節點插入到 curr 后面
copy.next = curr.next;
curr.next = copy;
// curr 指向下一個節點
curr = copy.next;
}
// 此時鏈表結構如下所示
// 1->1'->2->2'->3->3'->4->4'->5->5'->6->6'->NULL
// 2. 復制 random 節點
curr = head;
while (curr != null) {
Node copy = curr.next;
// copy 節點的 random 指向原節點的 random 節點的 copy 節點, 完成復制
if (curr.random != null) {
copy.random = curr.random.next;
}
curr = copy.next;
}
// 3. 將 copy 鏈表從原鏈表上斷開
Node sentinel = new Node(0);
curr = sentinel;
while (head != null) {
Node copy = head.next;
// 恢復原鏈表
head.next = copy.next;
// 構建copy鏈表
curr.next = copy;
// 游標后移
curr = curr.next;
head = head.next;
}
return sentinel.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143964.html
標籤：其他