首页 > 试题广场 >

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

[问答题]
找到单向链表中间那个元素,如果有两个则取前面一个
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)
//思路大家都知道,需要注意的一点就是,如果按照常规的快慢指针的思路,当有偶数个节点时,输出的中间节点是后一个,而不是前一个,所以需要稍微处理一下。
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)
发表于 2017-04-21 14:32:07 回复(0)
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)
先遍历单链表求出表长len,然后从头再次遍历表,但是设置遍历终点为(len+1)/2,即可找到。
发表于 2017-04-21 02:13:58 回复(0)