前提:这类问题,都不能借助其它数据结构或一些现成工具类。比如调用StringUtils.reverse(str)完成翻转,或者先入stack再出stack。仅使用最基本的分支/循环来实现最优解法。
一、字符串反转
java中字符串,其实就是一个字符数组,可以用数组的思路,首尾交换即可。
private String reverseString(String str) {
char[] arr = str.toCharArray();
for (int i = 0; i < arr.length / 2; i++) {
int j = arr.length - i - 1;
char temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
return new String(arr);
}
二、单链表反转
单链表只能从头节点开始1个个向后查找。这里有一个小技巧:通常会在头部加一个哑节点,不存放任何数据,只是为了方便快速找到头节点。
单链表的测试类如下:
class LinkNode {
public String value;
public LinkNode next;
public LinkNode(String v, LinkNode next) {
this.value = v;
this.next = next;
}
}
LinkNode buildTestLinkNode() {
LinkNode d = new LinkNode("d", null);
LinkNode c = new LinkNode("c", d);
LinkNode b = new LinkNode("b", c);
LinkNode a = new LinkNode("a", b);
LinkNode dummy = new LinkNode("dummy", a);
return dummy;
}
void printLinkNode(LinkNode head) {
while (head.next != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.print(head.value + "\n");
}
@Test
public void testPrintLinkNode() {
printLinkNode(buildTestLinkNode());
}
打印出来为:dummy->a->b->c->d
反转的思路如下:
从第2个有效节点开始,将其从链表中摘下来,然后放到哑节点后面,不断重复这个过程。
@Test
public void testReverseLinkNode() {
LinkNode dummy = buildTestLinkNode();
printLinkNode(dummy);
reverseLinkNode(dummy);
}
/**
* 单链表反转
* @param dummy
*/
private void reverseLinkNode(LinkNode dummy) {
if (dummy == null || dummy.next == null || dummy.next.next == null) {
return;
}
LinkNode prev = dummy.next;
LinkNode curr = prev.next;
while (true) {
prev.next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = prev.next;
printLinkNode(dummy);
if (curr == null) {
break;
}
}
}
输出结果:
dummy->a->b->c->d dummy->b->a->c->d dummy->c->b->a->d dummy->d->c->b->a