程序员代码面试指南 —— 链表问题(二)
程序员文章站
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;
}