876. 链表的中间结点 - 力扣（LeetCode）

Time: O(n)

Space:O(1)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
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;}
}

141. 环形链表 - 力扣（LeetCode）

/*** 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) {if (head == null || head.next == null) return false;ListNode slow = head;ListNode fast = head;while (fast!= null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) return true;}return false;}
}

142. 环形链表 II - 力扣（LeetCode）

/*** 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;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) break;}if (fast == null || fast.next == null) return null;while (head != slow) {head = head.next;slow = slow.next;}return head;}
}

143. 重排链表 - 力扣（LeetCode）

1. 找mid

2.reverse

3.重排

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public void reorderList(ListNode head) {if (head == null || head.next == null) return;ListNode first = head;ListNode mid = findMid(head);ListNode second = mid.next;mid.next = null;second = reverse(second);reorder(first, second);return;}private ListNode findMid(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}private ListNode reverse(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = reverse(head.next);head.next.next = head;head.next = null;return newHead;}private ListNode reorder(ListNode first, ListNode second) {ListNode dummy = new ListNode(0);ListNode cur = dummy;while (first != null && second != null) {cur.next = first;first = first.next;cur.next.next = second;second = second.next;cur = cur.next.next;}if (first != null) {cur.next = first;}if (second != null) {cur.next = second;}return dummy.next;}
}

课后作业：

234. 回文链表 - 力扣（LeetCode）

1.找中间节点

2.reverse后半段

3.对比两段是不是一样

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) return true;ListNode first = head;ListNode mid = findMid(head);ListNode second = mid.next;mid.next = null;second = reverse(second);return compare(first, second);}private ListNode findMid(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}private ListNode reverse(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = reverse(head.next);head.next.next = head;head.next = null;return newHead;}private boolean compare(ListNode first, ListNode second) {while (first != null && second != null) {if (first.val != second.val) return false;first = first.next;second = second.next;}return true;}}