目录

1、leetcode206. 反转链表

1.1、迭代

1.2、递归

2、获取中间点

3、应用场景

3.1、leetcode234. 回文链表

3.2、环形链表

3.3、相交链表

1、leetcode206. 反转链表

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

1.1、迭代

	public ListNode reverseList(ListNode head){ListNode newHead = null;while(head != null){ListNode nxt = head.next;head.next = newHead;newHead = head;head = nxt;}return newHead;}

1.2、递归

思路：
1、递归遍历链表
2、保留当前头节点,下一个节点将继续翻转
    3、翻转后返回新的链表头，且下一个节点为链表尾
4、链表尾的下一跳指向当前头节点，获得新的链表尾，尾部置null
应用场景：链表的逆序访问

	public ListNode reverseList(ListNode head){if(head == null|| head.next == null){return head;}ListNode newHead = reverseList(head.next);//下一个节点逆序后为链表尾部head.next.next = head;//链表尾部指向当前节点head.next = null;//新的尾部节点置null;return newHead;}

2、获取中间点

一次遍历获取链表的中间节点，使用快慢指针即可
中点的选取：
当前链表的节点数为奇数时，中点为对称点例如：1->2->3->4->5->null，中点为3。
当前链表的节点数为偶数时,中点可以在对称点左侧或者右侧，如：1->2->3->4->null，
中点为 2或者 4，此时代码实现有细微差别。
注意事项：链表的操作最忌空指针方访问，所以需要格外注意fast.next，fast.next.next 的访问    

	public ListNode middleNode(ListNode head){ListNode slow = head,fast= head;//while(fast != null && fast.next != null){//获取偶数链表对称点的右侧while(fast.next != null && fast.next.next != null){//获取偶数链表对称点的左侧fast = fast.next.next;slow = slow.next;}return slow;}

3、应用场景

3.1、leetcode234. 回文链表

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false示例 2:
输入: 1->2->2->1
输出: true

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：
1、将中间点将链表截断成两段;
2、右侧链表反转;
3、左右两侧链表匹配。

    public boolean isPalindrome(ListNode head) {if(head == null || head.next == null){return true;}ListNode middle = middleNode(head);ListNode right =  reverseList(middle.next);middle.next = null;ListNode left = head;while(right != null){//中点的位置位于对称点的左侧，右侧链表长度小于等于左侧if(left.val != right.val){return false;}else{left = left.next;right = right.next;}}return true;}public ListNode middleNode(ListNode head){ListNode slow = head,fast= head;while(fast.next != null && fast.next.next != null){//获取偶数链表对称点的左侧fast = fast.next.next;slow = slow.next;}return slow;}public ListNode reverseList(ListNode head){if(head == null|| head.next == null){return head;}ListNode newHead = reverseList(head.next);//下一个节点逆序后为链表尾部head.next.next = head;//链表尾部指向当前节点head.next = null;//新的尾部节点置null;return newHead;}

3.2、环形链表

....

3.3、相交链表

.....