文章 224
评论 6
浏览 200772
LinkedList - 24. Swap Nodes in Pairs

LinkedList - 24. Swap Nodes in Pairs

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;
    }

}

标题:LinkedList - 24. Swap Nodes in Pairs
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/07/26/1564073926712.html

Nothing just happens, it's all part of a plan.

取消