這裡面給出五道經典的連結清單題目
1. Leetcode206-反轉連結清單
https://leetcode-cn.com/problems/reverse-linked-list/
反轉一個單連結清單。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以疊代或遞歸地反轉連結清單。你能否用兩種方法解決這道題？
解法： 建立prev前向指針
- Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur,prev = head,None
while cur :
cur.next, prev, cur = prev, cur, cur.next
return prev
- Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode prev = null;
while(cur != null){
ListNode tmp = cur.next;
cur.next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
}
2. Leetcode24-兩兩交換連結清單中的節點
給定一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後的連結清單。
你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
示例:
給定 1->2->3->4, 你應該傳回 2->1->4->3.
解法：定義一個prev指針指向head，将head與head.next交換，prev指向下一個位置。
- Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode prev = new ListNode(0);
ListNode first = prev;
prev.next = head;
while (prev.next!=null && prev.next.next!=null) {
ListNode a = prev.next;
ListNode b = prev.next.next;
ListNode tmp = prev.next.next.next;
prev.next = b;
b.next = a;
a.next = tmp;
prev = a;
}
return first.next;
}
}
- Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
prev = ListNode(0)
ranger = prev
prev.next = head
while prev.next and prev.next.next:
a, b = prev.next,prev.next.next
prev.next, a.next, b.next = b, b.next,a
prev = a
return ranger.next
3. Leetcode141-環形連結清單
給定一個連結清單，判斷連結清單中是否有環。
為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：連結清單中沒有環。
進階：
你能用 O(1)（即，常量）記憶體解決此問題嗎？
解法：1. 硬做（1s内不斷next，沒有結束說明有環）2. set走一步查一次，時間O(N)，空間O(N) 3. 快慢指針,時間O(N)，空間O(1)
- Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// using fast&slow pointer
ListNode fast = head;
ListNode slow = fast;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
- Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = slow = head
while fast and slow and fast.next:
fast = fast.next.next
slow = slow.next
if fast==slow:
return True
return False
4.Leetcode-142環形連結清單 II
給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。
為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。
說明：不允許修改給定的連結清單。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：連結清單中沒有環。
解法：與上一題同樣是用快慢指針
- Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(fast!= null && slow!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
while(head!=fast){
head = head.next;
fast = fast.next;
}
return head;
}
}
return null;
}
}
- Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
fast = slow = head
while fast and slow and fast.next:
fast = fast.next.next
slow = slow.next
if fast==slow :
while fast != head:
fast = fast.next
head = head.next
return head
return None
5.Leetcode-25 K個一組翻轉連結清單
給你一個連結清單，每 k 個節點一組進行翻轉，請你傳回翻轉後的連結清單。
k 是一個正整數，它的值小于或等于連結清單的長度。
如果節點總數不是 k 的整數倍，那麼請将最後剩餘的節點保持原有順序。
示例 :
給定這個連結清單：1->2->3->4->5
當 k = 2 時，應當傳回: 2->1->4->3->5
當 k = 3 時，應當傳回: 3->2->1->4->5
說明 :
你的算法隻能使用常數的額外空間。
你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
題解：如下圖示意
- Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy, end = dummy;
dummy.next = head;
while (end.next != null) {
for (int i=0;i<k && end!=null;i++) {
end = end.next;
}
if (end == null) break;
ListNode next = end.next;
end.next = null;
ListNode start = pre.next;
pre.next = this.reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dummy.next;
}
public ListNode reverse(ListNode head) {
ListNode pre = null;
while (head != null) {
ListNode tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
}
- Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
pre = end = dummy
while(end.next):
i = 0
while(i<k and end):
i += 1
end = end.next
if not end:break
start = pre.next
next_group_start = end.next
end.next = None
pre.next = self.reverse(start)
start.next = next_group_start
pre = start
end = pre
return dummy.next
def reverse(self,head):
pre = None
while(head):
tmp = head.next
head.next = pre
pre = head
head = tmp
return pre