算法练习(1)-字符串/单链表反转
前提：这类问题，都不能借助其它数据结构或一些现成工具类。比如调用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
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-06-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读