Leetcode876.链表的中间节点

1.题目描述

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

2.解答

首先我的思路就是快慢指针,

  • 让两个指针p1,p2分别指向head,
  • p2每次向后走两步,p1每次向后走一步,

最后只需要处理while循环的判定条件就好了,

  • 如果p2.next == null,说明p2已经指向了奇数链表的最后一个节点

  • 如果p2 == null ,说明p2已经指向了偶数链表的最后一个节点后面的null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null)    return head;
        ListNode p1 = head,p2 = head;
        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }
}

我又想到了使用计数器的方法,

  • 首先遍历链表得到节点个数count,
  • 然后可以得到目标节点的位置,
  • 注意这里的ans应该是ans = count / 2 + 1的,但是在下面的while循环中,ans表示移动的次数,也就是应该少一次,想要移动到第三个节点的位置,那么只需要从头节点移动两次就可以了
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null) return head;
        int count = 0;
        ListNode temp = head;
        while(temp != null){
            count++;
            temp = temp.next;
        }
        temp = head;
        int ans = count / 2;
        while(ans > 0){
            temp = temp.next;
            ans--;
        }
        return temp;
    }
}

因为链表是不能使用下标访问的,所以我们可以将其放在一个数组中

但是缺点是开辟了额外的数组空间

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ArrayList<ListNode> arr = new ArrayList<>();
        ListNode temp = head;
        while(temp != null){
            arr.add(temp);
            temp = temp.next;
        }
        return arr.get(arr.size() / 2);
    }
}

3.总结

这道题算法链表最简单的一个了,果然我是虐菜小王子,希望不要沉迷于ac简单题的快感中, 实际上这是一点收获都没有的

还需要知道一个算法题目中约定俗称的东西就是,这里的头节点并不是我们认为的,那种不存实际有意义数据的节点,而是第一个链表的第一个节点。