首页 > 代码库 > Leetcode 线性表 Swap Nodes in Pairs

Leetcode 线性表 Swap Nodes in Pairs

2024-07-04 12:33:54   224人阅读

本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie


Swap Nodes in Pairs

 Total Accepted: 12511 Total Submissions: 39302

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

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

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.



题意：交换给定链表中的相邻节点,但不可以改变链表里的值
如1->2->3->4交换后为2->1->4->3
思路：
按题意中的扫描去改变每两个相邻节点的next指针的指向即可。
小技巧：
因为处理每两个相邻节点的时候，需要一个指针记录它们前一个节点，而头节点前面没有节点，
所以可设置一个dummy节点指向头指针，这样开头的两个节点的处理方式跟其它的相邻节点的处理方式就一样了
复杂度：时间O(n)，空间O(1)

/**
 * 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) return NULL;
    	ListNode *dummy = new ListNode(0); dummy->next = head;
    	ListNode *pre = dummy, *cur = head, *next = head->next;
    	while(cur && next){
    		ListNode *temp = next->next;
    		pre->next = next;
    		cur->next = next->next;
    		next->next = cur;
    		pre = cur;
    		cur = temp;
    		next = temp==NULL ? NULL : temp->next;
    	}
    	return dummy->next;
    }


联系
我们