[leetcode题解]24.Swap Nodes in Pairs(节点交换)

leetcode 第24题,将链表中相邻元素位置颠倒,题目要求不能改变元素节点中元素的值,只能改动节点位置。也就是要求在链表中删除插入。

python代码如下:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        :author: 凌风技术站-iaccepted
        """
        if head is None or head.next is None:
            return head
        pre = ListNode(-1)
        tail = pre
        
        p = head
        while p is not None:
            #找k个元素,p为首元素,q为第k个元素的下一个位置
            k = 2
            q = p
            while q is not None and k > 0:
                q = q.next
                k -= 1
                
            #如果 k > 0则表示不够k个元素
            if k > 0:
                tail.next = p
                break
            #把这k个元素逆序插入已有链表尾部
            ed = p
            while p != q:
                t = p.next
                p.next = tail.next
                tail.next = p
                p = t
            tail = ed
        return pre.next

c++代码如下:

class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        ListNode *pre = new ListNode(-1);
        ListNode *tail = pre;
        
        int k = 2;
        ListNode *p = head;
        while(p != NULL)
        {
            ListNode *q = p;
            for (int i = 0; i < k && q != NULL; ++i)q = q->next;
            
            ListNode *end = p;
            
            while(p != q)
            {
                ListNode *t = p->next;
                p->next = tail->next;
                tail->next = p;
                p = t;
            }
            tail = end;
        }
        tail->next = NULL;
        return pre->next;
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]24.Swap Nodes in Pairs(节点交换)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/102.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注