找到单向链表中间那个元素，如果有两个则取前面一个

[问答题]

shaul

struct list_a* get_list_mid(struct list_a* list) {
    struct list_a* fast = list;
    struct list_a* slow = list;

    while (1) {
        if (fast)
            fast = fast->next;
        else
            break;

        if (fast)
            fast = fast->next;
        else
            break;

        if (fast)
            slow = slow->next;
    }

    return slow;
}

发表于 2018-06-20 17:11:29 回复(0)

戾

p,q指针同时指向首节点，然后p = p->next，同时 q = q->next->next ,直到 q->next == NULL 或者 q->next->next == NULL ,则 p指向中点

编辑于 2017-04-24 13:00:56 回复(1)

BugFree

//思路大家都知道，需要注意的一点就是，如果按照常规的快慢指针的思路，当有偶数个节点时，输出的中间节点是后一个，而不是前一个，所以需要稍微处理一下。
public static Node searchMiddleNode(Node head) {
		if (head == null || head.next == null)
			return head;
		// 一般查找问题都是两个指向头节点的指针（快慢指针）共同移动。
		int length = getListLength(head);
		Node fast = head;
		Node slow = head;
		Node temp = slow;//如果有两个中间节点，取前一个
		while (fast != null && fast.next != null) {
			temp = slow;
			fast = fast.next.next;
			slow = slow.next;
		}
		temp.next = null;
		slow.next = null;
		//System.out.print("temp.value: " + temp.value + " slow.value: " + slow.value);
		if(length % 2 != 0)
			return slow;
		else
			return temp;
	}

发表于 2017-04-25 10:53:30 回复(2)

farm_cat

发表于 2017-04-21 14:32:07 回复(0)

牛客4805747号

if(head.next == null || head.next.next == null)
    return head;
node pre = head;
node cur = head.next.next;
while(cur.next != null && cur.next.next != null) { //每增加两个节点，中节点后移一个
    pre = pre.next;
    cur = cur.next.next;
}
return pre.val;

发表于 2017-04-21 10:51:35 回复(0)