1、链表反转

模板：

1.1 反转链表

 1 class Solution {
 2     public ListNode reverseList(ListNode head) {
 3         ListNode prev = null;
 4         ListNode curr = head;
 5         while (curr != null) {
 6             ListNode next = curr.next;
 7             curr.next = prev;
 8             prev = curr;
 9             curr = next;
10         }
11         return prev;
12     }
13 }

 

1.2 反转某个区间（leff, right）的节点

K 个一组翻转链表

反转链表 II

 1 public ListNode[] myReverse(ListNode head, ListNode tail) {
 2     ListNode prev = tail.next;
 3     ListNode p = head;
 4     while (prev != tail) {
 5         ListNode nex = p.next;
 6         p.next = prev;
 7         prev = p;
 8         p = nex;
 9     }
10     return new ListNode[]{tail, head};
11 }

 

 

2、快慢指针

比较两种方式 快指针的初始位置，以及循环条件

2.1 链表的中间结点

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

 

2.2 环形链表

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;
    }
}