单链表反转

数据结构第一节就是链表。链表由多个node节点组成，每个node节点包含数据和一个指针。指针指向下一个节点。

组装链表

经常问单链表的算法，那你首先要定下来链表的结构，而不是直接思考算法。为了方便使用，我们固定一个哨兵作为
头节点。数据节点都在头节点之后。

/** * @author Ryan Miao */ @Data static class Node { //是否是head节点。 true-YES private Boolean head; private Integer data; private Node next; }

那么，我们创建的一个节点是这样的

Node head = new Node(); head.setData(-1); head.setHead(true); Node node = new Node(); node.setData(123); node.setHead(false);

所以，我们首先要创建一个数组1 2 3 4 5 6 7 8 9。

private Node toNode(Integer[] arr) { Node head = new Node(); head.setData(-1); head.setHead(true); Node tail = head; for (int i = 0; i < arr.length; i++) { Node node = new Node(); node.setData(arr[i]); node.setNext(null); node.setHead(false); // append to tail tail.next = node; // set tail to next tail = node; } return head; } private Node makeNode(Integer... arr) { return toNode(arr); } makeNode(1,2,3,4,5,6,7,8,9);

为了方便展示，写一个链表遍历的方法，用来打印链表结构：

private static void printNode(Node head) { Node p = head.next; while (p != null) { System.out.print(p.getData()); p = p.next; if (p != null) { System.out.print("->"); } } System.out.println(); } 链表插入

插入节点tmp. 先找到要插入的位置，然后构造插入节点tmp。让tmp指向后面的节点。前一个节点指向tmp。

@Test public void testInsert() { Node node = makeNode(3, 4, 5, 6, 7, 8, 9); System.out.println("--------origin--------"); printNode(node); // insert 10 between 4 and 5 Node p = node; while (p != null) { if (p.getData() == 4) { Node tmp = new Node(); tmp.setData(10); tmp.next = p.next; p.next = tmp; break; } p = p.next; } System.out.println("--------inserted--------"); printNode(node); }

打印结果：

--------origin-------- 3->4->5->6->7->8->9 --------inserted-------- 3->4->10->5->6->7->8->9 链表删除

链表删除首先要找到要删除的节点，将pre指向next。

@Test public void deleteNode() { Node node = makeNode(3, 4, 5, 6, 7, 8, 9); System.out.println("--------origin--------"); printNode(node); //delete 5 Node head = node; Node p = node; while (p != null) { if (p.getData() == 5) { //if the first is 5, skip head.next = p.next; break; } Node pre = p; p = p.next; if (p != null && p.getData().equals(5)) { pre.next = p.next; break; } } System.out.println("---------deleted---------"); printNode(head); }

打印结果

--------origin-------- 3->4->5->6->7->8->9 ---------deleted--------- 3->4->6->7->8->9 链表反转

链表最常问的算法就是反转了。目前有两个常见的方式，一个是头插入法，新建一个head，遍历原来的head，插入新链表。

一个是就地反转。将链表看成两部分，左边是新链表，右边是旧链表。每次从右边取出一个，插入昨天的头部，最终全部插入左边。实现整体反转。

头插法

private Node headInsert(Node head) { if (head.next == null) { return head; } // new node head final Node newHead = new Node(); newHead.setHead(true); newHead.setData(head.getData()); // pointer Node p = head; while (p.next != null) { // 暂存取下的节点 Node tmp = p.next; // 原来的链表指针移动到下一个 p.next = p.next.next; // 取下的节点 指向 新链表的头节点之后 tmp.next = newHead.next; // 新链表指向 插入的节点 newHead.next = tmp; } return newHead; }

打印结果：

=========origin========== 3->4->5->6->7->8->9 ---------head insert-------- 9->8->7->6->5->4->3 就地反转

private Node inverse(Node head) { if (head == null) { return null; } // 左边链表的tail节点 Node leftTail = head.next; if (leftTail == null) { return head; } // 左边链表的head节点 Node leftHead = head.next; // 当前的指针右边原始链表的第一个节点 Node pCur = leftTail.next; if (pCur == null) { leftTail.next = head; head.next = null; return leftTail; } while (pCur != null) { // 左边链表tail指向 右边链表的下个节点 leftTail.next = pCur.next; // 右边链表的当前第一个节点指向昨天链表的head pCur.next = leftHead; // head指向插入的节点 head.next = pCur; // 右边链表指针移动下一个节点 pCur = leftTail.next; } return head; }

打印结果：

=========origin========== 3->4->5->6->7->8->9 ---------inverse-------- 9->8->7->6->5->4->3