这里面给出五道经典的链表题目
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