java链表快慢指针找到中间节点

本文主要是介绍java链表快慢指针找到中间节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、加虚拟节点

1、找到中间节点的上一个节点

1  2  3  4  5  6  7  8  null

             |               |

           slow         fast

1  2  3  4  5  6  7  null

         |           |

      slow      fast

ListNode dummy = new ListNode();
dummy = head;
ListNode slow = dummy,fast = dummy;
while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;
}

2、在偶数个时找到的是后一半的第一个

1  2  3  4  5  6  7  8  null

                 |                  |

               slow            fast

1  2  3  4  5  6  7  null

             |                 |

           slow           fast

ListNode dummy = new ListNode();
dummy = head;
ListNode slow = dummy,fast = dummy;while(fast != null){slow = slow.next;fast = fast.next;if(fast != null) fast = fast.next;}

二、不加虚拟节点

1、找到中间节点的下一个节点

适合归并排序时用

1  2  3  4  5  6  7  8  null

                 |                  |

               slow            fast

1  2  3  4  5  6  7  null

                 |             |

               slow       fast

ListNode slow = head,fast = head;while(fast != null){slow = slow.next;fast = fast.next;if(fast != null) fast = fast.next;}

2、在偶数时找到前一半的最后一个

1  2  3  4  5  6  7  8  null

             |                    |

           slow              fast

1  2  3  4  5  6  7  null

             |                |

           slow          fast

ListNode slow = head,fast = head;
while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;
}

这篇关于java链表快慢指针找到中间节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---