LeetCodeチェーンテーブル特集6:チェーンテーブルとダブルポインタ
8989 ワード
例題:LeetCode第19題:チェーンテーブルの最後からN番目のノードを削除する
転送ゲート:英語のURL:19.Remove Nth Node From End of List,中国語URL:19.チェーンテーブルの最後からN番目のノードを削除します.
チェーンテーブルが与えられ、チェーンテーブルの最後からn番目のノードが削除され、チェーンテーブルのヘッダノードが返される.
例:
説明:
与えられたn保証は有効である.
ステップ:
スキャンを使って実現してみてもいいですか?
考え方:スナップポインタを使用します.実は末尾の要素からどのように離れるかを把握すれば、簡単です.また、境界値の選択に注意してください.実際には、値と正確な値は、不注意なエラーを避けるために、具体的な例を挙げることができます.また,チェーンヘッダノードの操作に関しては,一般に仮想ノードが導入され,議論の可能性を低減するのが一般的である.
Pythonコード:
練習1:LeetCode 61題:回転チェーンテーブル
転送ゲート:英文URL:61.Rotate List,中国語URL:61.チェーン時計を回す.
チェーンテーブルを指定し、チェーンテーブルを回転させ、チェーンテーブルの各ノードをk個の位置に右に移動させ、kは非負の数である.
例1:
例2:
考え方:問題自体は難しくないが、細部を処理しなければならない.
1、必ずチェーンテーブルの全長を求めなければならない.
2、総长を求める时、ついでに末尾の结点をマークして、しかも末尾の结点のnext指を头の结点に指して行って、环を形成して、さもなくば空の指针の异常が现れやすいです;
3、いったいどれだけのpreポインタがどれだけ歩かなければならないのか、1～2つの具体的な例を挙げて持ち込めばわかります.
Pythonコード:
練習2:LeetCode第143題:チェーンテーブルの並べ替え
転送ドア:143.チェーンテーブルを並べ替える.
単一チェーンテーブルL:L 0→L 1→…→Ln-1→Lnを与え、これを並べ替えて、L 0→Ln→L 1→Ln-1→L 2→Ln-2→…
単純にノード内部の値を変えるのではなく、実際にノード交換を行う必要があります.
例1:
例2:
Javaコード:
練習3:LeetCode第234題:回文チェーンテーブル
転送ドア:234.回文チェーン
チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:
例2:
進級:O(n)時間の複雑さとO(1)空間の複雑さでこの問題を解決できますか?
解の鍵:チェーンテーブルの中間位置のノードを見つけて、いくつかの関連する処理をします.特に注意しなければならないのは、いずれの方法でも、いくつかの細部の問題をよく考慮し、具体的な例を挙げて、図面を描いて符号化の実現を助けることができる.
構想1:中間位置からチェーンテーブルを反転し,個々に比較する.
Javaコード:
構想2:チェーンテーブルの中間ノードを探す過程で,遅いノードが前方に遍歴するとき,遍歴した値をスタックに入れる.
Javaコード:
(本節終了)
転送ゲート:英語のURL:19.Remove Nth Node From End of List,中国語URL:19.チェーンテーブルの最後からN番目のノードを削除します.
チェーンテーブルが与えられ、チェーンテーブルの最後からn番目のノードが削除され、チェーンテーブルのヘッダノードが返される.
例:
: 1->2->3->4->5, n = 2.
， 1->2->3->5.
説明:
与えられたn保証は有効である.
ステップ:
スキャンを使って実現してみてもいいですか?
考え方:スナップポインタを使用します.実は末尾の要素からどのように離れるかを把握すれば、簡単です.また、境界値の選択に注意してください.実際には、値と正確な値は、不注意なエラーを避けるために、具体的な例を挙げることができます.また,チェーンヘッダノードの操作に関しては,一般に仮想ノードが導入され,議論の可能性を低減するのが一般的である.
Pythonコード:
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def findKthToTail(self, pListHead, k):
"""
:type pListHead: ListNode
:type k: int
:rtype: ListNode
"""
if pListHead is None:
return None
fast = pListHead
# 1：
for _ in range(k - 1):
fast = fast.next
if fast is None:
return None
slow = pListHead
# 2：
while fast.next:
slow = slow.next
fast = fast.next
return slow
練習1:LeetCode 61題:回転チェーンテーブル
転送ゲート:英文URL:61.Rotate List,中国語URL: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
考え方:問題自体は難しくないが、細部を処理しなければならない.
1、必ずチェーンテーブルの全長を求めなければならない.
2、総长を求める时、ついでに末尾の结点をマークして、しかも末尾の结点のnext指を头の结点に指して行って、环を形成して、さもなくば空の指针の异常が现れやすいです;
3、いったいどれだけのpreポインタがどれだけ歩かなければならないのか、1～2つの具体的な例を挙げて持ち込めばわかります.
Pythonコード:
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or k <= 0:
return head
#
node = head
#
counter = 1
while node.next:
node = node.next
counter += 1
node.next = head
k = k % counter
node = head
# counter - k - 1
for _ in range(counter - k - 1):
node = node.next
new_head = node.next
node.next = None
return new_head
練習2:LeetCode第143題:チェーンテーブルの並べ替え
転送ドア:143.チェーンテーブルを並べ替える.
単一チェーンテーブルL:L 0→L 1→…→Ln-1→Lnを与え、これを並べ替えて、L 0→Ln→L 1→Ln-1→L 2→Ln-2→…
単純にノード内部の値を変えるのではなく、実際にノード交換を行う必要があります.
例1:
1->2->3->4, 1->4->2->3.
例2:
1->2->3->4->5, 1->5->2->4->3.
Javaコード:
/**
* @author liwei
* @date 18/7/5 9:36
*/
public class Solution2 {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode anotherHead = slow.next;
// 1：
slow.next = null;
// 2：
ListNode reverseList = reverseList(anotherHead);
// 3：
int k = 0;
mergeTwoList(head, reverseList, k);
}
private ListNode mergeTwoList(ListNode head1, ListNode head2, int k) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
// k % 2 == 0
if ((k & 1) == 0) {
head1.next = mergeTwoList(head1.next, head2, ++k);
return head1;
} else {
head2.next = mergeTwoList(head1, head2.next, ++k);
return head2;
}
}
private ListNode reverseList(ListNode head) {
ListNode preNode = null;
ListNode curNode = head;
while (curNode != null) {
ListNode nextNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = nextNode;
}
return preNode;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
Solution2 solution2 = new Solution2();
ListNode head = new ListNode(nums);
solution2.reorderList(head);
System.out.println(head);
}
}
練習3:LeetCode第234題:回文チェーンテーブル
転送ドア:234.回文チェーン
チェーンテーブルが返信チェーンテーブルであるかどうかを判断してください.
例1:
: 1->2
: false
例2:
: 1->2->2->1
: true
進級:O(n)時間の複雑さとO(1)空間の複雑さでこの問題を解決できますか?
解の鍵:チェーンテーブルの中間位置のノードを見つけて、いくつかの関連する処理をします.特に注意しなければならないのは、いずれの方法でも、いくつかの細部の問題をよく考慮し、具体的な例を挙げて、図面を描いて符号化の実現を助けることができる.
構想1:中間位置からチェーンテーブルを反転し,個々に比較する.
Javaコード:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
/**
* https://leetcode-cn.com/problems/palindrome-linked-list/description/
*
* @author liwei
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow ，
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// pre
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
public static void main(String[] args) {
int[] nums = {1, 2, 0, 2, 1};
Solution solution = new Solution();
ListNode head = new ListNode(nums);
boolean palindrome = solution.isPalindrome(head);
System.out.println(palindrome);
}
}
構想2:チェーンテーブルの中間ノードを探す過程で,遅いノードが前方に遍歴するとき,遍歴した値をスタックに入れる.
Javaコード:
import java.util.Stack;
/**
* @author liwei
*/
public class Solution2 {
// ， ，
// slow
// 1，2，3，4，5
// slow
// 1，2，3，4
/**
* @param head
* @return
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
Stack stack = new Stack<>();
ListNode fast = head;
ListNode slow = head;
stack.add(slow.val);
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
stack.add(slow.val);
}
if (fast.next == null) {
//
stack.pop();
}
slow = slow.next;
while (slow != null) {
if (stack.pop() != slow.val) {
return false;
}
slow = slow.next;
}
return true;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
int[] nums = {1, 2, 3, 2, 1};
ListNode head = new ListNode(nums);
boolean palindrome = solution2.isPalindrome(head);
System.out.println(palindrome);
}
}
(本節終了)