将给定的链表中每两个相邻的节点交换一次,返回链表的头指针
例如,
给出1->2->3->4,你应该返回链表2->1->4->3。
你给出的算法只能使用常量级的空间。你不能修改列表中的值,只能修改节点本身。
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; } }
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; } }
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; } } };
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; } };
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; } };
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; } }
/** * 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; } };
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; } };
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; } }
/**
* 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;
}
};
/*两个指针分别指向奇数和偶数位置,一个指针指向前一次的结尾处 先调换位置,再将其挂到上一次结尾处 之后继续调整三个指针位置即可 */ 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; } };
// 一对一对的逆置 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; } };
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; } }
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; } }
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; } };
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; } };//用递归即可
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