欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

程序员代码面试指南 —— 链表问题(二)

程序员文章站 2024-02-27 15:54:45
...

题目:给定一个链表的头节点head,请你判断是否为回文结构
例如:1 —> 2 —> 1 ture
1 —> 2 —> 2 —> 1 true
1 —> 2 —> 3 flase
思路:可以使用栈这种数据结构,可以将整个单向链表分为前半区和后半区,然后将前半区的数据入栈,遍历后半区的数据,将后半区的数据和栈进行比较,当栈空或者链表空,则说明是回文
需要确定的问题:如何进行分区,矛盾所在是奇数链表和偶数链表的问题,
两种策咯:(1)奇偶分情况讨论,(2)屏蔽奇偶差异
这里代码采用第二种:

public class ReverChain {
  public static void main(String[] args) {
    Node head = new Node(1);
    Node node1 = new Node(2);
    Node node2 = new Node(1);
    head.next = node1;
    node1.next = node2;
    System.out.println(isRever(head));
  }
 
  private static boolean isRever(Node head) {
    int time = 0;
    Node h = head;
    while (h != null) {
      h = h.next;
      time++;
    }
 
    // 屏蔽奇偶差异
    double point = (double) time / 2;
    int end = (int) Math.floor(point);
    int begin = (int) Math.ceil(point) + 1;
 
    int i = 0;
    Stack<Node> stack = new Stack<>();
    while (i < end) {
      stack.push(head);
      head = head.next;
      i++;
    }
 
    // 屏蔽奇偶差异
    if (begin != end + 1) {
      head = head.next;
    }
 
    i = begin;
    while (i <= time) {
      if (stack.peek().value == head.value) {
        stack.pop();
        head = head.next;
      } else {
        break;
      }
      i++;
    }
    if (stack.isEmpty()) {
      return true;
    }
    return false;
  }
}

题目二:将单链表按某值划分成左边小,中间相等,右边大的形式
描述: 给定一个单项链表头节点head,节点的值类型是整形,再给定一个整数pivot,实现一个调整链表的函数,将链表调整成左边部分的值都小于pivot的节点,中间部分的值都等于pivot的节点,右边部分都是值大于pivot的节点。
代码:

public static void main(String[] args) {
  Node head = new Node(1);
  Node node1 = new Node(4);
  Node node2 = new Node(2);
  Node node3 = new Node(3);
  Node node4 = new Node(5);
  Node node5 = new Node(7);
  head.next = node1;
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = node5;
  int pivot = 3;
  Node h = sortChain(head, pivot);
  while (h != null) {
    System.out.println(h.value + " ");
    h = h.next;
  }
}
 
private static Node sortChain(Node head, int pivot) {
  // 0 为逻辑值,拼接时删除
  Node big = new Node(0);
  Node equals = new Node(0);
  Node small = new Node(0);
  // 记录初始位置
  Node bigStart = big;
  Node equalsStart = equals;
  Node smallStart = small;
 
  // 分离
  while (head != null) {
    if (head.value == pivot) {
      equals.next = new Node(head.value);
      equals = equals.next;
    } else if (head.value > pivot) {
      big.next = new Node(head.value);
      big = big.next;
    } else {
      small.next = new Node(head.value);
      small = small.next;
    }
    head = head.next;
  }
 
  // 拼接
  Node res = new Node(0);
  Node resStart = res;
 
  if (smallStart.next != null) {
    res.next = smallStart.next;
    res = small;
  }
  if (equalsStart.next != null) {
    res.next = equalsStart.next;
    res = equals;
  }
  if (bigStart.next != null) {
    res.next = bigStart.next;
    res = big;
  }
  return resStart.next;
}