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.
代码不是最简的,处理head的部分明显可以和后面合并。关键记住无论思路多清晰都需要模拟一下。
/** * 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) { ListNode *first = head; if(head == NULL) return NULL; ListNode *second = head -> next; ListNode *temp; if(second != NULL) { head = second; temp = first; first -> next = second -> next; second -> next = first; first = first->next; if(first == NULL ||first -> next == NULL )return head; second = first ->next; temp ->next = second; } while(first != NULL && second != NULL) { temp = first; first -> next = second -> next; second -> next = first; first = first->next; if(first == NULL ||first -> next == NULL )return head; second = first ->next; temp ->next = second; } return head; } };