[LC 24]. Swap Nodes in Pairs

LinkedList的题关键是想清楚操作过程。例如本题,既然是swap pair,那么成对和不成对两种情况可以分开考虑。如果不成对,那么意味着list到结尾了,所以放在最后考虑,循环里只考虑成对的情况。对当前的一个pair,例如v1->v2 变成 v2->v1,v2.next = v1.next 是不会造成任何错误的,v1.next需要注意,是下一对swap后的头,可以在下一个循环中赋值。


public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newhead = head.next;
    ListNode nextpair = head;
    ListNode lastend = null;
    while (nextpair != null && nextpair.next != null){ // only for pairs
        ListNode node1 = nextpair;
        ListNode node2 = nextpair.next;
        nextpair = nextpair.next.next; // head of next pair

        node2.next = node1; // swap the current pair
        if (lastend != null) {
            lastend.next = node2; // finish pointing the end of last pair to the head of this pair
        }
        lastend = node1; // remember the end of this pair
    }
    if (lastend != null) {
        lastend.next = nextpair; // if current pair is solo node,
// no need to swap, only point the end of last pair to the current node;
// if there is no more pairs,
// set the end of last pair to null, which is also the head of the current pair
    }
    return newhead;
}

需要牵扯到前,中,后,三个node的问题,也可以考虑一种通用的做法,就是在最开始加dummy node。这个问题中,pointer每往后移动一个pair,原来指向dummy的pointer就会指向前一个pair的tail。考虑以下code,比第一段可能更加清晰:

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) { //依然只考虑pair
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            cur.next = second; // 依次是cur,first和second的next赋值
            first.next = second.next;
            second.next = first;
            cur = cur.next.next;
        }
       return dummy.next;//之前已经将current pair的tail的next赋值成了下一个pair的head,如果下一个pair不完整,则什么都不需要做。
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s