首页 > 试题广场 >

交互链表节点

[编程题]交互链表节点
  • 热度指数：13121 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
将给定的链表中每两个相邻的节点交换一次，返回链表的头指针
例如,
给出1->2->3->4，你应该返回链表2->1->4->3。
你给出的算法只能使用常量级的空间。你不能修改列表中的值，只能修改节点本身。
示例1

输入

{1,2}

输出

{2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
韩迅头像 韩迅 
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode start = new ListNode(0);
        start.next = head;
        for(ListNode cur = start; cur.next!=null&&cur.next.next!=null; cur=cur.next.next){
            cur.next = swap(cur.next, cur.next.next);
        }
        return start.next;
    }
    public ListNode swap(ListNode head1, ListNode head2){
        head1.next = head2.next;
        head2.next = head1;
        return head2;
    }
}

发表于 2016-06-05 12:58:25 回复(1)
Java
詆調壹點头像 詆調壹點 
public class Solution {
    public static ListNode swapPairs(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		for (ListNode pre = dummy, cur = head, temp; cur != null && cur.next != null; pre = cur, cur = cur.next) {
			temp = cur.next;
			cur.next = temp.next;
			temp.next = pre.next;
			pre.next = temp;
		}
		return dummy.next;
	}
}

发表于 2016-11-18 01:02:10 回复(0)
静下心来，学习头像 静下心来，学习
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode tmp = head.next.next;
        ListNode newHead = head.next;
        newHead.next=head;
        head.next=swapPairs(tmp);
        return newHead;
    }
}
发表于 2019-05-19 14:38:14 回复(4)
LinuX18头像 LinuX18 
/// 用递归简洁点
class Solution 
{
public:
    /// 分析一下，使用递归
    ListNode *swapPairs(ListNode *head) 
    {
       if(!head || !head->next)   /// 空或者仅有一个节点
           return head;
       ListNode *newHead = head->next;
       head->next = swapPairs(newHead->next);
       newHead->next = head;
       return newHead;
    }
};

发表于 2017-07-14 21:26:16 回复(0)
BlackMamba24头像 BlackMamba24 
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (head == NULl || head->next == NULL)
            return head;
        else if (head->next->next == NULL) {
            ListNode* pNext = head->next;
            pNext->next = head;
            head->next = NULL;
            return pNext;
        } else {
            ListNode* pNext = head->next;
            ListNode* newHead = pNext->next;
            pNext->next = head;
            head->next = swapPairs(newHead);
            return pNext;
        }
    }
};

发表于 2016-06-24 09:44:33 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head == NULL || head->next == NULL)
        	return head;
        
        ListNode L(-1);
        L.next = head;			//头结点前增加一个结点 
		ListNode *f = &L;	//f为p的前一个结点 
        ListNode *p = head;		//p为当前结点 
        while(p != NULL && p->next != NULL)
        {
        	ListNode *q = p->next;	//q为p的后一个结点 
        	p->next = q->next;		//p指向q的后一结点 
        	q->next = p;			//q指向p 
        	f->next = q;			//f指向p 
        	f = p;					//f变为p 
        	p = p->next;			//p后移一个结点 
		}
		return head;
    }
};

发表于 2017-08-06 04:48:30 回复(2)
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class Solution {
public:
  // Recursive
  ListNode* swapPairs(ListNode* head) {
    // recursion exit condition
    if (!head || !head->next) return head;
    
    auto new_head = head->next;
    head->next = swapPairs(new_head->next);
    new_head->next = head;
    return new_head;
  }
  
  // Iterative
  ListNode* swapPairsII(ListNode* head) {
    ListNode dummy{0}, *pre = &dummy;
    dummy.next = head;

    while (pre->next && pre->next->next) {
      ListNode *p = pre->next, *q = p->next;
      pre->next = q;
      p->next = q->next;
      q->next = p;
      pre = p;
    }

    return dummy.next;
  }
  
};

发表于 2021-10-01 09:31:53 回复(0)
Java
Mono_Chrome头像 Mono_Chrome 
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur != null && cur.next != null) {
            ListNode pNext = cur.next;
            cur.next = pNext.next;
            pNext.next = cur;
            pre.next = pNext;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}
发表于 2019-11-05 19:06:58 回复(0)
菜鸡准备转岗头像 菜鸡准备转岗 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(!head || !head->next){
            return head;
        }
        ListNode *h = new ListNode(-1);
        h->next = head;
        ListNode *cur=head, *rear=head->next, *pre=h;
           //循环交换指针，注意循环终止条件（其中rear!=NULL跟单数有关）
        while(cur && rear){
            cur->next = rear->next;
            rear->next = cur;
            pre->next = rear;
            //next 
            pre = cur;
            cur = cur->next;
            if(cur)
                rear = cur->next;
        }
        return h->next;
    }
};

发表于 2019-06-29 15:26:35 回复(0)
zbbsyx头像 zbbsyx 
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode* dummpy = new ListNode(0), *p = dummpy, *q = NULL;
        dummpy -> next = head;
        while (p -> next && p -> next -> next){
            q = p -> next;
            p -> next = q -> next;
            q -> next = q -> next -> next;
            p -> next -> next = q;
            p = p -> next -> next;
        }
        return dummpy -> next;
    }
};

发表于 2019-05-28 14:11:01 回复(0)
Butterfliesflyaway↘头像 Butterfliesflyaway↘ 
public class Solution {
    public ListNode swapPairs(ListNode head) {
        //若头结点为空，或链表只有一个节点，则返回head本身
        if(head==null || head.next==null) return head;
        //若链表有两个及以上的节点时，关键在于修改两两节点间的next指针关系
        ListNode newHead = new ListNode(0); //辅助节点
        newHead.next = head;
        ListNode p1 = newHead;
        while(p1.next!=null && p1.next.next!=null) {
            //将辅助节点与要交换的两节点，在稿纸上画出每一步的指针改变时的断开与指向关系，可得下面的逻辑
            ListNode temp1 = p1.next;
            p1.next = p1.next.next;
            ListNode temp2 = temp1.next;
            temp1.next = p1.next.next;
            temp2.next = temp1;
            //交换完毕后，辅助节点向后走两位
            p1 = p1.next.next;
        }
        return newHead.next;
    }
}

发表于 2019-01-04 10:09:07 回复(0)
C/C++
黄汉韬头像 黄汉韬 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (NULL == head) {
            return NULL;
        }

        ListNode *new_head = new ListNode(0);
        new_head->next = head;
        ListNode *front = new_head;
        ListNode *end = head;

        while (end != NULL && end->next != NULL) {
            ListNode *temp = end->next->next;
            front->next = end->next;
            end->next->next = end;
            end->next = temp;

            front = end;
            end = end->next;
        }

        return new_head->next;
    }
};
发表于 2017-12-07 14:57:09 回复(0)
xcx920317头像 xcx920317 
/*两个指针分别指向奇数和偶数位置，一个指针指向前一次的结尾处
先调换位置，再将其挂到上一次结尾处
之后继续调整三个指针位置即可
*/
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head == NULL)return head;
        if(head->next == NULL)return head;
        ListNode*ret = head->next;
        head->next = ret->next;
        ret->next = head;
        ListNode*odd=head->next;
        ListNode*tail=head;
        while(odd&&odd->next){
            ListNode*even = odd->next;
            odd->next=even->next;
            even->next=odd;
            tail->next=even;
            tail=odd;
            odd=odd->next;
        }
        return ret;
    }
};
//如果大侠不怕晕非要用两个指针的话：
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head == NULL)return head;
        if(head->next == NULL)return head;
        ListNode*ret = head->next;
        head->next = ret->next;
        ret->next = head;
        ListNode*tail=head;
        while(tail->next&&tail->next->next){
            ListNode*even = tail->next->next;
            tail->next->next=even->next;
            even->next=tail->next;
            tail->next=even;
            tail=even->next;
        }
        return ret;
    }
};

编辑于 2017-07-05 00:23:27 回复(0)
C/C++
Dragon3头像 Dragon3 
//  一对一对的逆置
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode h(-1);
        h.next = head;
        ListNode* prev = &h;
        ListNode* node = head;
        while(node!=NULL && node->next!=NULL) {
            ListNode* tmp = node->next;
            node->next = tmp->next;
            tmp->next = node;
            prev->next = tmp;
            prev = node;
            node = prev->next;
        }
        return h.next;
    }
};

编辑于 2017-06-29 17:22:54 回复(0)
Java
Holiday_12138头像 Holiday_12138 
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode next = cur.next;
        while(next != null && next.next != null) {
            cur.next = next.next;
            next.next = cur.next.next;
            cur.next.next = next;
            cur = next;
            next = next.next;
        }
        return dummy.next;
    }
}

发表于 2017-06-03 16:38:12 回复(0)
...王嘉廉睿头像 ...王嘉廉睿 
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null)
            return null;
        if(head.next==null)
            return head;
        ListNode i=head;//两两节点值互换
        ListNode j=head.next;//
        int value;
        value=i.val;
        i.val=j.val;
        j.val=value;
        while(i.next!=null&&j.next!=null&&i.next.next!=null&&j.next.next!=null){
            i=i.next.next;
            j=j.next.next;
            value=i.val;
            i.val=j.val;
            j.val=value;
        }
        return head;
    }
}

发表于 2016-10-27 21:34:17 回复(0)
firsthead头像 firsthead 
class Solution {
public:
   ListNode *swapPairs(ListNode *head) {
		if (head == nullptr || head->next == nullptr)
		{
			return head;
		}

		ListNode *dummpy = new ListNode(0);
		dummpy->next = head;
		ListNode *n1 = dummpy;
		ListNode *n2 = head;
		while (n1->next != nullptr && n1->next->next != nullptr)
		{
			n1->next = n2->next;
			n2->next = n2->next->next;
			n1->next->next = n2;

			n1 = n1->next->next;
			n2 = n2->next;
		}
		return dummpy->next;
	}
};

发表于 2016-09-01 09:32:08 回复(0)
Java
木丶年华头像 木丶年华
//写的比较复杂，但思想简单
public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        while(cur != null && cur.next != null){ //如果最后只有一个链点就直接返回，不需要交换
            ListNode next = cur.next.next; //next判断是否是最后两个链表点
            if(next != null){
                pre.next = cur.next;
                cur.next = next;
                pre.next.next = cur;
                pre = cur;
            }else{
                pre.next = cur.next;
                pre.next.next = cur;
                cur.next = null; //最后要置于null，不然尾部会形成循环
            }
            cur = cur.next;
        }
        return dummy.next;
    }
发表于 2018-05-28 20:54:56 回复(0)
haodadegua头像 haodadegua 




class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
    if(head==nullptr||head->next==nullptr)
        return head;
    ListNode*pre=head;
    ListNode*cur=head->next;
    ListNode*nex=cur->next;
    cur->next=pre;
    pre->next=swapPairs(nex);
    return cur;
    }
};//用递归即可

发表于 2018-03-30 22:28:23 回复(0)
Python 3
HHHChen77头像 HHHChen77
python  模拟交换操作（代码略长哈） 
class Solution:
    def swapPairs(self , head ):
        if not head&nbs***bsp;not head.next:
            return head
        # 定义虚结点头
        dummy = move = ListNode(0)
        # 成对指针转移
        pre, cur = head, head.next
        # 遍历链表
        while cur:
            # 拆分指向
            pre.next = cur.next
            cur.next = pre
            # 确定指向
            move.next = cur
            move = pre
            # 下一对
            pre = pre.next
            # 没有下一对了
            if not pre:
                break
            cur = pre.next
        # 返回交换完成的链表
        return dummy.next


发表于 2021-09-04 10:38:02 回复(0)
提交观点

问题信息

链表
难度：
89条回答 17701浏览

热门推荐

通过挑战的用户

查看代码

相关试题

交互链表节点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号