<commit_before>---
layout: post
title: 蚂蚁金服在线笔试题 - 链表两两反转
date: 2016-10-20
categories: 笔试面试
tags: [笔试,算法与数据结构]
description: 通告一下，我已不再每天写千字文，准备采用以下的方法进行练习，由于文章篇幅较长，链接较多，建议到简书或博客进行阅读。

---

## 问题

>// 一个链表：a->b->c->d->e
>// 每两个元素进行反转：b->a->d->c->e

>// 输入链表头指针
>// 输出：反转后的链表头指针
>// 要求：不新建节点

## 解答
```java
public class Main {

	public static class Node {
		public final String name;
		private Node next;
		public Node(String name) {
			this.name = name;
		}
		public void setNext(Node next) {
			this.next = next;
		}
		public Node getNext() {
			return this.next;
		}
		@Override
		public String toString() {
			return this.name;
		}
	}

	public static Node revertList(Node node) {
		if (node == null) {
			return null;
		}
		// 存储结果的头节点
		Node result = node;
		// 当前节点的上一个节点
		Node lastNode = null;
		// 当前节点的上上一个节点
		Node oldNode = null;
		int i = 1;
		while (node != null) {
			if (i % 2 != 0) {
			    // 奇数位，只需平移指针
				oldNode = lastNode;
				lastNode = node;
				node = node.getNext();
			} else {
			    // 偶数位考虑元素反转
				if (oldNode == null) {
				    // 前二个元素反转，无需考虑oldNode，但要注意result赋值
					lastNode.setNext(node.getNext());
					node.setNext(lastNode);
					result = node;
				} else {
				    // 3，4... 反转
					oldNode.setNext(node);
					lastNode.setNext(node.getNext());
					node.setNext(lastNode);
				}
				// 这里lastNode已经和Node反转了，所以只需更新oldNode和Node
				oldNode = node;
				node = lastNode.getNext();
			}
			i++;
		}
		return result;
	}

	public static void main(String[] args) {
	
		Node a = new Node("a");
		Node b = new Node("b");
		a.setNext(b);
		Node c = new Node("c");
		b.setNext(c);
		Node d = new Node("d");
		c.setNext(d);
		Node e = new Node("e");
		d.setNext(e);

		Node result = revertList(a);

		while (result != null) {
			System.out.print(result.name + "->");
			result = result.getNext();
		}
	}
}

```
<commit_msg>Update 2016-10-20-list-revert.md<commit_after>---
layout: post
title: 蚂蚁金服在线笔试题 - 链表两两反转
date: 2016-10-20
categories: 笔试面试
tags: [笔试,算法与数据结构]
description: 通告一下，我已不再每天写千字文，准备采用以下的方法进行练习，由于文章篇幅较长，链接较多，建议到简书或博客进行阅读。

---

## 问题

> // 一个链表：a->b->c->d->e
> // 每两个元素进行反转：b->a->d->c->e
> // 输入链表头指针
> // 输出：反转后的链表头指针
> // 要求：不新建节点

## 解答
```java
public class Main {

	public static class Node {
		public final String name;
		private Node next;
		public Node(String name) {
			this.name = name;
		}
		public void setNext(Node next) {
			this.next = next;
		}
		public Node getNext() {
			return this.next;
		}
		@Override
		public String toString() {
			return this.name;
		}
	}

	public static Node revertList(Node node) {
		if (node == null) {
			return null;
		}
		// 存储结果的头节点
		Node result = node;
		// 当前节点的上一个节点
		Node lastNode = null;
		// 当前节点的上上一个节点
		Node oldNode = null;
		int i = 1;
		while (node != null) {
			if (i % 2 != 0) {
			    // 奇数位，只需平移指针
				oldNode = lastNode;
				lastNode = node;
				node = node.getNext();
			} else {
			    // 偶数位考虑元素反转
				if (oldNode == null) {
				    // 前二个元素反转，无需考虑oldNode，但要注意result赋值
					lastNode.setNext(node.getNext());
					node.setNext(lastNode);
					result = node;
				} else {
				    // 3，4... 反转
					oldNode.setNext(node);
					lastNode.setNext(node.getNext());
					node.setNext(lastNode);
				}
				// 这里lastNode已经和Node反转了，所以只需更新oldNode和Node
				oldNode = node;
				node = lastNode.getNext();
			}
			i++;
		}
		return result;
	}

	public static void main(String[] args) {
	
		Node a = new Node("a");
		Node b = new Node("b");
		a.setNext(b);
		Node c = new Node("c");
		b.setNext(c);
		Node d = new Node("d");
		c.setNext(d);
		Node e = new Node("e");
		d.setNext(e);

		Node result = revertList(a);

		while (result != null) {
			System.out.print(result.name + "->");
			result = result.getNext();
		}
	}
}

```

{'fraction_non_alphanumeric': 0.16097823165815642, 'fraction_numerical': 0.009137328675087342, 'mean_word_length': 2.5413891531874406, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7127319', 'n_tokens_mistral': 1994, 'n_tokens_neox': 1869, 'n_words': 319}