LinkedList - 24. Swap Nodes in Pairs

ppxai

发布于 2020-09-23 17:22:55

2660

发布于 2020-09-23 17:22:55

文章被收录于专栏：皮皮星球

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

思路：

链表的翻转实现题，题目意思是翻转相邻的两个节点，题目难点在于容易产生断链的情况。所有链表的题目，基本都是先做一个dummy节点去指向头结点，然后再去用其他指针操作链表的时候，就很方便。题目可以扩展为每隔k个节点翻转一次。

代码：

java：

/**

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null && curr.next != null) {
            // 先保存下curr的下一个节点
            ListNode currNext = curr.next;  
            
            curr.next = currNext.next;   
            currNext.next = curr;  
            prev.next = currNext;  
            
            prev = curr;
            curr = curr.next;
        }
        
        return dummy.next;
    }

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019年07月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法