思路相对简单，考察代码实现能力及其整洁高效。
206.Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
思路：把当前节点的指针指向前面节点（助记：调转枪口）
需要两个指针，一个记录当前节点，一个记录前面节点
while循环到链表结束
测试用例：输入的链表头指针是nullptr
输入的链表只有一个节点
输入的链表有多个节点
code:
class Solution {
public ListNode reverseList(ListNode head) {//返回类型为ListNode
ListNode prev = null;//定义前驱节点为空
ListNode curr = head;//定义当前节点为头节点
while (curr != null) {//当前节点不为空时，一直循环至链表结束
ListNode nextTemp = curr.next;//标记出下一个操作的节点，防止断链
curr.next = prev;//当前节点指针调转枪口指向前驱节点
prev = curr;//当前节点完成后改为前驱节点
curr = nextTemp;//现有下一个节点改为当前需要操作的节点
}
return prev; //返回前面节点
}
}
-
Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
思路：链表交换相邻元素
三个指针：相邻两个元素+前一个元素
代码不超过十行
测试用例：输入的链表头指针是nullptr
输入的链表只有一个节点
输入的链表有多个节点
code:
public class Solution {
public ListNode swapPairs(ListNode head) {
if ((head == null)||(head.next == null))
return head;
ListNode n = head.next;
head.next = swapPairs(head.next.next);
n.next = head;
return n;
}
}
image.png
- Linked List Cycle
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
思路：法一：从前往后推，直到遇到空指针（硬做，性能差）
法二：每个节点用set存储，到新节点对set判重（O(n*1)）
法三：快慢指针法（快指针走两步，慢指针走一步，若相遇则有环）O(n)（龟兔赛跑追击问题）
code:
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;//初始化慢指针
ListNode fast = head.next;//初始化快指针
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
- Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
思路：第一步：确定是否包含环，同上题
第二步：快慢指针相遇的节点一定在环中，从相遇节点出发，一边继续向前移动一边计数，再次回到这个节点时，即得环中节点数。
第三步：找环的入口：定义两个指针指向头节点，若环有n个节点，则指针一先向前移动n个节点，然后俩指针以相同速度向前移动，当指针二指向环的入口节点时，指针一绕着环走了一圈又回到了入口节点。
code:
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
- Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
思路：法一：栈
法二：尾插法
法三：递归
code:
class Solution{
public ListNode reverseKGroup(ListNode head, int k) {
ListNode curr = head;
int count = 0;
while (curr != null && count != k) { // find the k+1 node
curr = curr.next;
count++;
}
if (count == k) { // if k+1 node is found
curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
// head - head-pointer to direct part,
// curr - head-pointer to reversed part;
while (count-- > 0) { // reverse current k-group:
ListNode tmp = head.next; // tmp - next head in direct part
head.next = curr; // preappending "direct" head to the reversed list
curr = head; // move head of reversed part to a new node
head = tmp; // move "direct" head to the next node in direct part
}
head = curr;
}
return head;
}
}
