算法题:链表的中间结点。java实现
时间: 2023-05-28 08:03:38 浏览: 88
以下是Java实现:
```
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
```
算法思路:
使用两个指针,一个指针每次走一步,另一个指针每次走两步,当快指针到达链表末尾时,慢指针刚好到达链表的中间位置。
相关问题
第9关:查找链表倒数第k个结点
题目描述:给定一个链表,输出该链表倒数第k个节点,如果k大于链表长度则返回空。
算法思路:使用双指针,先让第一个指针移动k-1个节点,然后再让第一个指针和第二个指针同时移动,当第一个指针到达链表结尾时,第二个指针指向的就是倒数第k个节点。
参考代码实现(Python):
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findKthToTail(head, k):
if head is None or k <= 0:
return None
# 定义两个指针,初始都指向头结点
p1 = p2 = head
# 让第一个指针移动k-1个节点
for i in range(k-1):
if p1.next is None:
return None
p1 = p1.next
# 两个指针同时移动,直到第一个指针到达链表结尾
while p1.next is not None:
p1 = p1.next
p2 = p2.next
return p2
```
参考代码实现(Java):
```java
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
// 定义两个指针,初始都指向头结点
ListNode p1 = head;
ListNode p2 = head;
// 让第一个指针移动k-1个节点
for (int i = 0; i < k-1; i++) {
if (p1.next == null) {
return null;
}
p1 = p1.next;
}
// 两个指针同时移动,直到第一个指针到达链表结尾
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
```
Java代码实现构造一颗三叉链表表示的二叉树,实现插入结点,实现采用先根、中根、后根、层次算法遍历二叉树,输出二叉树结点值
以下是Java代码实现构造一颗三叉链表表示的二叉树,实现插入结点,实现采用先根、中根、后根、层次算法遍历二叉树,输出二叉树结点值的实现:
```java
// 三叉链表表示的二叉树结点类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
this.parent = null;
}
}
// 三叉链表表示的二叉树类
class BinaryTree {
TreeNode root;
// 插入结点
public void insert(int val) {
TreeNode node = new TreeNode(val);
if (root == null) {
root = node;
} else {
TreeNode parent = null;
TreeNode current = root;
while (current != null) {
parent = current;
if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
if (val < parent.val) {
parent.left = node;
node.parent = parent;
} else {
parent.right = node;
node.parent = parent;
}
}
}
// 先根遍历
public void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.val + " ");
preOrder(node.left);
preOrder(node.right);
}
}
// 中根遍历
public void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.val + " ");
inOrder(node.right);
}
}
// 后根遍历
public void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.val + " ");
}
}
// 层次遍历
public void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
// 测试代码
public class Main {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
System.out.println("先根遍历:");
tree.preOrder(tree.root);
System.out.println();
System.out.println("中根遍历:");
tree.inOrder(tree.root);
System.out.println();
System.out.println("后根遍历:");
tree.postOrder(tree.root);
System.out.println();
System.out.println("层次遍历:");
tree.levelOrder(tree.root);
System.out.println();
}
}
```
输出结果为:
```
先根遍历:
5 3 2 4 7 6 8
中根遍历:
2 3 4 5 6 7 8
后根遍历:
2 4 3 6 8 7 5
层次遍历:
5 3 7 2 4 6 8
```