链表中奇数位和偶数位的置换

痛定思痛。 2023-07-24 13:16 161阅读 0赞

# 1. 题目描述 #

[两两交换链表中的节点][Link 1]

# 2. 题目分析 #

1.链表如下所示：  
![在这里插入图片描述][20200411225136787.png]  
2. 建立一个root结点，并建立两个结点指针，如图所示：  
![在这里插入图片描述][20200411225607721.png]  
注意：这里的0结点，是JAVA建立root结点是附带的：`ListNode root = new ListNode(0);`  
![在这里插入图片描述][20200411225904341.png]  
3. 思路如下：  
将p1.next连接到p2.next（0----->2），如下：  
![在这里插入图片描述][20200411230901930.png]  
将p2.next连接到p1.next.next（1----->3），如下：  
![在这里插入图片描述][20200411231322105.png]  
将p1.next.next连接到p2（相当于2----->1），如图所示：  
![在这里插入图片描述][20200411231642924.png]  
千万不要链表越界，注意p2指针的范围`while(p2 != null && p2.next != null)`

# 3. 题目代码 #

class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            if(head == null){
        
                return head;
            }
            ListNode root = new ListNode(0);
            root.next = head;
            ListNode p1 = root;
            ListNode p2 = root.next;
    		while(p2 != null && p2.next != null) {
        
    			p1.next = p2.next;
    			p2.next = p1.next.next;
                p1.next.next = p2;
    			p1 = p2;
    			p2 = p2.next;
    		}
    		return root.next;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[20200411225136787.png]: /images/20230528/16661777a3894e37837110c77e240ead.png
[20200411225607721.png]: /images/20230528/45a4c573fe154193a249ff789370f3d9.png
[20200411225904341.png]: /images/20230528/24f8c9e3a2be48abb6eeee94f2d33b66.png
[20200411230901930.png]: /images/20230528/2ca2b8b51e284e37b972ec053f3cc78a.png
[20200411231322105.png]: /images/20230528/a2b59959fb7f42b8b9b7efb1d59fbc5b.png
[20200411231642924.png]: /images/20230528/a290cf2b5c9f476bacd7b99cbee0e0b2.png