经度算法：逆转单向链表

Dear 丶 2022-03-16 08:44 185阅读 0赞

逆转单向链表，听上去是一个非常简单的题目，但如果在面试中遇到它，能够将它完完整整没有 bug 的写出来是着实需要费一番功夫的。期望在那急短的笔试题环节就轻松搞定这道题，那真是非常有算法天赋的人才能做到的事。天才总是极少数的，多数都是像我这样的庸才。单向的链表，不同于 Java 里面的 LinkedList（双向的链表）。链表中每个节点之间通过 next 指针串接起来，会有一个链表头和链表尾指针 hold 住整个链表。

逆转的任务：* head -> a -> b -> c -> d <- tail * 》》 *head -> d -> c -> b -> a <- tail*

![20190326214859324.png][]

class Node<T> {
    	T value;
    	Node<T> next;
    	Node(T value) {
    		this.value = value;
    	}
    }
    class ReverseLinkedList<T> {
        Node<T> head, tail;
        public ReverseLinkedList(T... values) {
            for (T value : values) {
                if (tail == null) {// 第一个节点                
                    head = tail = new Node<>(value);
                } else {
                    // 后面的节点往链表尾部追加
                    Node<T> oldTail = tail;
                    oldTail.next = tail = new Node<>(value);
                }
            }
        }
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            Node<T> cur = head;
            while (cur != null) {
                sb.append(cur.value);
                cur = cur.next;
                if (cur != null) {
                    sb.append(',');
                }
            }
            sb.append(']');
            return sb.toString();
        }
    }
    ReverseLinkedList<Integer> link = new ReverseLinkedList<>(1,2,3,4);

![20190326215611528.png][]

### 循环调整next 指针 ###

循环调整 next 指针是最容易想到的方法，但是要将指针精确地逆转正确其实并不容易，精致的做法是：使用了三个临时局部变量 cur、next 和 nextnext。

![2019032621591730.png][]

//是不是很绕，总当心哪里会有遗漏
    public ReverseLinkedList<T> reverseByLoop() {
        // 空链表或者单元素都无需处理
    	if (head == tail) {
    		return this;
    	}
    	Node<T> cur = head;
    	Node<T> next = cur.next;
    	while (next != null) {
    		Node<T> nextnext = next.next;
    		next.next = cur;
    		cur = next;
    		next = nextnext;
    	}
    	tail = head;
    	tail.next = null;
    	head = cur;
    	return this;
     }

### 递归逆转 ###

递归的思想来解决这个问题也是一个很好的主意，只不过当链表特别长时，调用栈会很深，就会抛出臭名昭著的异常StackOverflowException。

![20190326220540466.png][]

public ReverseLinkedList<T> reverseByRecursive() {
    	Node<T> oldTail = tail;
    	tail = reverseFrom(head);
    	tail.next = null;
    	head = oldTail;
    	return this;
    }
    private Node<T> reverseFrom(Node<T> from) {
     	if (from == tail) {
    	  return from;
    	}
    	Node<T> end = reverseFrom(from.next);
    	end.next = from;
    	return from;
    }

好的算法确实很值得借鉴。![84954103][]

[20190326214859324.png]: /images/20220316/78e48c4f379d4a9399976a5ef75034f9.png
[20190326215611528.png]: /images/20220316/c7c8caa285404b48afb5790282a13ad6.png
[2019032621591730.png]: /images/20220316/b2ca3596a1ac4150b8d26bf0f770bb8a.png
[20190326220540466.png]: /images/20220316/e17945827adb4dc78059f643430c0eb2.png
[84954103]: /images/20220316/97088415248e41509475d0503104a35f.png