【算法】反转单链表，两两反转

2017-01-31 Algorithm 阅读量

问题一、反转单链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

链表结点定义如下，这里使用的是Java描述：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

思路

如何把一个单链表进行反转？

方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。
方法2：用头插法新建链表。我们知道创建链表的两种方式：头插法和尾插法，头结点插入法形成的链表是和输入顺序相反的，尾节点插入法形成的链表是和输入顺序相同的，所以其中一种方法是，遍历原链表，然后用原链表的输出元素顺序用头结点插入法新建链表，这样新建的链表就是反转后的链表。
方法3：就地反转链表。使用3个指针遍历单链表，逐个链接点进行反转。

1、借助数组逆序反转

由于题目并没有要求必须原地反转，因此可以借助外部空间实现。这里可以将单链表储存为数组，然后按照数组的索引逆序进行反转。但是，此方式比较浪费空间，而且需要两次遍历，效率不占优势。

/**
 * 使用数组拷贝的方式反转单链表
 */
public static ListNode reverseList1(ListNode head){
    if(head == null) return null;

    //转移到数组存储(这里用ArrayList方便些)
    List<ListNode> nodeList = new ArrayList<ListNode>();
    while (head != null) {
        nodeList.add(head);
        head = head.next;
    }

    int startIndex = nodeList.size() - 1;
    for (int i = startIndex; i >= 0; i--) {
        ListNode node = nodeList.get(i);
        if (i == 0) {
            node.next = null;
        } else {
            node.next = nodeList.get(i - 1);
        }
    }
    // 现在头结点是原来的尾节点
    head = nodeList.get(startIndex);
    return head;
}

2、头插法新建链表来反转

这个方法和第一个借助数组一样，需要额外一倍的空间来存储生成的新链表

/**
 * 头插法建立新链表，达到反转目的
 */
public static ListNode reverseList2(ListNode head){
    if(head == null) return null;

    ListNode previous = null;   //记录上个节点
    ListNode newHead = null;    //头插法的新头节点

    while(head != null){
        newHead = new ListNode(head.val);   //新建头结点
        newHead.next = previous;

        previous = newHead;
        head = head.next;   //下一个节点
    }
    return newHead;
}

3、三个指针就地反转

使用三个指针指向：当前节点A，下个节点B，以及下下个节点C。

遍历时，如下首先记录下下个节点C，然后节点B的指针断开并指向A。然后移动进入下一组。

A -> B -> C ->D -> E

A <- B C ->D -> E

整个过程只需遍历链表一次，效率提高不少，且需要的外部空间也较第一种方法要少很多，实现代码如下：

/**
 * 使用三个指针原地反转单链表
 */
public static ListNode reverseList(ListNode head){
    if(head == null) return null;

    ListNode a = head;      //当前节点A
    ListNode b = head.next; //下个节点B
    ListNode temp;          //下下个节点C

    //头结点的指针先清空
    head.next = null;

    //有可能链表只有一个节点，所以需要看b是否为null
    while(b != null){
        temp = b.next;  // 记录C节点
        b.next = a;     // a->b 反向

        if(temp == null){
            break;
        }
        a = b;      //移动到下一个节点
        b = temp;
    }
    return b == null ? a : b;
}

单元测试

测试代码如下：

public class Test {

    public static void main(String[] args) {
        ListNode a1 = new ListNode(5);
        ListNode a2 = new ListNode(4);
        ListNode a3 = new ListNode(30);
        ListNode a4 = new ListNode(78);
        ListNode a5 = new ListNode(99);

        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        //反转单链表
        ListNode node = reverseList(a1);

        //打印输出结果
        while (node != null){
            System.out.print(node.val);
            node = node.next;
            System.out.print(node != null ? "->" : "");
        }
    }
}

问题二、单链表两两反转

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

解答

仿照前面的单链表反转，我们最少需要三个指针： current，next， nextNext。
　　
分析：我们需要两个“指针”指着当前要反转的两个值current和next。两两反转后，我们还需要记录下一个的值，即反转A和B后，需要记录 C 值，我们才能够不断向下走，直到到达链表末端。所以，需要另一个指向下一个值的“指针”，即nextNext。反转以后，A的下一个是C， 但是，实际上，A的下一个应该是D，所以，每次反转时，我们需要更新前一个值的下一个值，也就是说把 A -> C 改成 A -> D，所以需要prev指针。所以，要完成这个操作，我们总共需要4个“指针”。具体看代码：
　　
所以最终我们一共需要分析四个指针： prev，current，next， nextNext。

/**
 * 单链表两两反转
 *
 *      已知一个链表：a->b->c->d->e
 * 每两个元素进行反转：b->a->d->c->e
 */
public static ListNode reversePairedList(ListNode head){
    if(head == null) return null;

    ListNode a = head;          //当前节点A
    ListNode b = head.next;     //下个节点B
    ListNode temp;              //下下个节点C
    ListNode previous = null;   //上一组的尾指针，在下一组反转后需要改变
    ListNode newHead = b == null ? a : b;

    while(b != null){
        temp = b.next;  // 记录C节点
        b.next = a;     // a->b 反向
        a.next = temp;
        if(previous != null){
            previous.next = b;
        }

        if(temp == null){
            break;
        }
        previous = a;
        a = temp;       //移动到下一组
        b = temp.next;
    }
    return newHead;
}