题目: 两两交换链表中的节点

分析

两结点交换

交换链表结点的方法一共涉及到三个结点，需要交换的这两个结点以及这两个结点前序的结点，比如这三个结点分别是firstNode，secondNode，preNode。交换方法如下：

preNext.next=secondNode;

secondNode.next=firstNode;

firstNode.next=postNode;

哨兵法

该题涉及到链表的节点交换，链表的节点交换除了交换了两个节点之外，还涉及到这两个节点的前驱节点和后节点，因为最前面两个节点交换的时候没有前节点，需要特殊处理，为了简化操作流程，可以在头部增加哨兵节点。

哨兵结点是值在链表头部新增一个结点，从而简化头结点特殊的处理逻辑。

该题只需要按顺序遍历一次链表，所以时间复杂度是O（N）。

空间复杂度，因为需要增加一个虚拟的头节点作为哨兵节点，所以空间复杂度是O（1）。

递归法

该问题是可以划分同构子问题的，例如最前方两个节点交换之后，后面节点作为一个子问题和原始问题是同样的结构。类似的问题都是可以使用递归解决的。

递归调用的逻辑如下：

• 如果输入的链表大于两个节点，则分为两部分，第一部分是前面2个节点，第二部分是剩余的节点。
  • 前面两个节点交互位置，然后剩余的节点继续调用递归逻辑。
  • 将两部分的结果链接起来就是问题的结果。
• 如果输入的链表只有两个节点。
  • 将两个节点交换问题返回。
• 如果输入的链表只有一个节点。
  • 则直接返回。

该问题的递归解决方案时间复杂度是Θ（N）。

解题

哨兵法

哨兵的代码如下：

public class PairNodeSwap {

    static class LinkNode{
        public int value;
        public LinkNode nextNode;

        public LinkNode(int value){
            this.value = value;
        }

        public static LinkNode getInstance(Integer[] input){
            LinkNode header = new LinkNode(input[0]);
            LinkNode current = header;
            for(int i = 1; i < input.length; i ++){
                LinkNode next = new LinkNode(input[i]);
                current.nextNode = next;
                current = next;
            }

            return header;
        }

        public String toString(){
            LinkNode header = this;
            StringBuilder sb = new StringBuilder("");
            while(true){
                sb.append(header.value);
                if((header = header.nextNode) != null){
                    sb.append("->");
                }else{
                    break;
                }
            }

            return sb.toString();
        }
    }

    public static LinkNode swapPairNode(LinkNode header){
        LinkNode dummp = new LinkNode(0);
        dummp.nextNode = header;

        LinkNode current = dummp;
        while(true) {
            LinkNode firstNode = current.nextNode;
            if(firstNode == null){
                break;
            }
            LinkNode secondNode = firstNode.nextNode;
            if(secondNode == null){
                break;
            }
            LinkNode thirdNode = secondNode.nextNode;

            current.nextNode = secondNode;
            secondNode.nextNode = firstNode;
            firstNode.nextNode = thirdNode;

            current = firstNode;
        }

        return dummp.nextNode;
    }
}

递归

递归的代码如下：

type node struct {
	date int
	next *node
}

func RecursionSolution(list *node) *node {
	if list == nil{
		return list
	}else if list.next == nil{
		return list
	}else if list.next.next == nil{
		first := list
		second := list.next

		first.next = nil
		second.next = first
		return second
	}else{
		firstPart := list
		secondPart := list.next.next

		first := list
		second := list.next

		first.next = nil
		second.next = first
		firstPart = second

		secondPart = RecursionSolution(secondPart)
		firstPart.next.next = secondPart

		return firstPart
	}
}