题目:Swap Nodes in Pairs
交换相邻的两个节点。
思路:
两个指针指向相邻的两个节点,交换他们。
注意:
链表节点少于2个直接返回。
1->2->3->4->5->6
p:2,q:3;
交换3,4的顺序:
p->next = q->next;
p = p->next;
q->next = p->next;
p->next = q;
/******************************************************************************* 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. *******************************************************************************/ #include<stdio.h> struct ListNode { int val; struct ListNode *next; }; /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* swapPairs(struct ListNode* head) { if(head == NULL || head->next == NULL)return head;//少于两个节点 struct ListNode* p = head->next;//先交换开头两个节点 head->next = p->next; p->next = head; head = p; p = p->next; struct ListNode* q = p->next; while(p->next != NULL && q->next != NULL){ p->next = q->next; p = p->next; q->next = p->next; p->next = q; q = q->next; p = p->next; } return head; } void display(struct ListNode* p){ while(p != NULL){ printf("%d ",p->val); p = p->next; } printf(" "); } void main(){ int n = 7; struct ListNode* head = NULL; for(int i = 0;i < n;i++){ struct ListNode* p = (struct ListNode* )malloc(sizeof(struct ListNode)); p->val = i; p->next = head; head = p; } display(head); head = swapPairs(head); struct ListNode* p = NULL; while(head != NULL){ p = head; head = head->next; printf("%d ",p->val); free(p); } }