2020.10.22每日复习

剑指Offer 24.反转链表在这里插入图片描述 **分析** 876.链表的中间节点在这里插入图片描述 **分析**

剑指Offer 24.反转链表

分析

采用双指针，令后指针元素的指针域指向前指针的元素，再令指针分别前进一位，依次类推 /** * 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 pre = null; ListNode cur = head; while(cur != null) { ListNode temp = cur.next;//临时存储后指针原本的指向 cur.next = pre;//令后元素指向前元素 pre = cur;//前指针往后移 cur = temp;//后指针往后移 } return pre; //递归 if(head == null || head.next == null) return null; ListNode pre = reverseList(head.next); head.next.next = head; head.next = null; return pre; } }

876.链表的中间节点

分析

采用快慢指针，快指针一次前进两个单位，慢指针前进一个单位，当快指针到头时，此时的慢指针指向的就是中间元素。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode middleNode(ListNode head) { ListNode first = head;//快指针 ListNode slow = head;//慢指针 while(first != null && first.next != null) { first = first.next.next;//一次前进两步 slow = slow.next;//每次前进一步 } return slow; } }