(100分)- 单向链表中间节点（Java & JS & Python）

题目描述

求单向链表中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。

输入描述

第一行 链表头节点地址 后续输入的节点数n

后续输入每行表示一个节点，格式 节点地址 节点值 下一个节点地址(-1表示空指针)

输入保证链表不会出现环，并且可能存在一些节点不属于链表。

输出描述

单向链表中间的节点值

用例

输入	00010 4 00000 3 -1 00010 5 12309 11451 6 00000 12309 7 11451
输出	6
说明	无

输入	10000 3 76892 7 12309 12309 5 -1 10000 1 76892
输出	7
说明	无

题目解析

用例1示意图如下

JS本题可以利用数组模拟链表 

基于链表数据结构解题

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let head;
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    [head, n] = lines[0].split(" ");
  }

  if (n && lines.length === n - 0 + 1) {
    lines.shift();

    const nodes = {};

    lines.forEach((line) => {
      const [addr, val, nextAddr] = line.split(" ");
      nodes[addr] = [val, nextAddr];
    });

    console.log(getResult(head, nodes));

    lines.length = 0;
  }
});

function getResult(head, nodes) {
  const linkedlist = [];

  let node = nodes[head];
  while (node) {
    const [val, next] = node;

    linkedlist.push(val);
    node = nodes[next];
  }

  const len = linkedlist.length;

  const mid = len % 2 === 0 ? len / 2 : Math.floor(len / 2);

  return linkedlist[mid];
}

Java算法源码

在Java中，LinkedList的get(index)方法时间复杂度为O(n)而非O(1)，这种情况下更推荐使用ArrayList来实现。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String head = sc.next();
    int n = sc.nextInt();

    HashMap<String, String[]> nodes = new HashMap<>();
    for (int i = 0; i < n; i++) {
      String addr = sc.next();
      String val = sc.next();
      String nextAddr = sc.next();
      nodes.put(addr, new String[] {val, nextAddr});
    }

    System.out.println(getResult(head, nodes));
  }

  public static String getResult(String head, HashMap<String, String[]> nodes) {
    //    LinkedList<String> link = new LinkedList<>();
    ArrayList<String> link = new ArrayList<>();

    String[] node = nodes.get(head);
    while (node != null) {
      String val = node[0];
      String next = node[1];

      link.add(val);
      node = nodes.get(next);
    }

    int len = link.size();
    int mid = len / 2;
    return link.get(mid);
  }
}

Python算法源码

# 输入获取
head, n = input().split()

nodes = {}
for i in range(int(n)):
    addr, val, nextAddr = input().split()
    nodes[addr] = [val, nextAddr]


# 算法入口
def getResult(head, nodes):
    linkedlist = []
    node = nodes.get(head)

    while node is not None:
        val, next = node
        linkedlist.append(val)
        node = nodes.get(next)

    length = len(linkedlist)
    mid = int(length / 2)

    return linkedlist[mid]


# 算法调用
print(getResult(head, nodes))

链表结构与快慢指针解法

链表作为一种非连续存储的数据结构，本身并不具备真正的索引概念。但在实际应用中，我们经常需要访问特定位置的元素，因此大多数编程语言都为链表提供了"伪索引"功能。以Java的LinkedList为例，虽然提供了get(index)方法，但其底层实现是通过遍历链表节点（逐个访问next属性）来定位目标元素，这意味着每次索引访问都需要O(n)的时间复杂度。

在链表相关问题中，一个常见考点是如何在未知链表长度的情况下找到中间节点。这时，快慢指针算法就派上用场了。

快慢指针的工作原理是：

• 设置两个指针同时遍历链表
• 慢指针每次移动1个节点
• 快指针每次移动2个节点 当快指针到达链表末尾时，慢指针正好位于中间节点位置（对于奇数长度链表取正中间节点，偶数长度则取中间偏右的节点）。

虽然本题给出了节点数量，但这些节点可能属于不同的链表结构，因此实际链表长度仍是未知的。由于题目要求的中间节点定义与快慢指针的结果完全一致，所以采用快慢指针算法是最优解决方案。

Java算法源码

import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String head = sc.next();
    int n = sc.nextInt();

    HashMap<String, String[]> nodes = new HashMap<>();
    for (int i = 0; i < n; i++) {
      String addr = sc.next();
      String val = sc.next();
      String nextAddr = sc.next();
      nodes.put(addr, new String[] {val, nextAddr});
    }

    System.out.println(getResult(head, nodes));
  }

  public static String getResult(String head, HashMap<String, String[]> nodes) {
    String[] slow = nodes.get(head);
    String[] fast = nodes.get(slow[1]);

    while (fast != null) {
      slow = nodes.get(slow[1]);

      fast = nodes.get(fast[1]);
      if (fast != null) {
        fast = nodes.get(fast[1]);
      } else {
        break;
      }
    }

    return slow[0];
  }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let head;
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    [head, n] = lines[0].split(" ");
  }

  if (n && lines.length === n - 0 + 1) {
    lines.shift();

    const nodes = {};

    lines.forEach((line) => {
      const [addr, val, nextAddr] = line.split(" ");
      nodes[addr] = [val, nextAddr];
    });

    console.log(getResult(head, nodes));

    lines.length = 0;
  }
});

function getResult(head, nodes) {
  let slow = nodes[head];
  let fast = nodes[slow[1]];

  while (fast) {
    slow = nodes[slow[1]];

    fast = nodes[fast[1]];
    if (fast) {
      fast = nodes[fast[1]];
    } else {
      break;
    }
  }

  return slow[0];
}

Python算法源码

# 输入获取
head, n = input().split()

nodes = {}
for i in range(int(n)):
    addr, val, nextAddr = input().split()
    nodes[addr] = [val, nextAddr]


# 算法入口
def getResult(head, nodes):
    slow = nodes.get(head)
    fast = nodes.get(slow[1])

    while fast is not None:
        slow = nodes.get(slow[1])

        fast = nodes.get(fast[1])
        if fast is None:
            break
        else:
            fast = nodes.get(fast[1])

    return slow[0]


# 算法调用
print(getResult(head, nodes))