首页 > 代码库 > 63. Swap Nodes in Pairs && Rotate List && Remove Nth Node From End of List
63. Swap Nodes in Pairs && Rotate List && Remove Nth Node From End of List
Swap Nodes in Pairs
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 要改变位置。还要有一个 pre 指针。
/** * 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 *pre = NULL, *p = head; while(p && p->next) { ListNode *q = p->next; p->next = q->next; q->next = p; if(pre == NULL) head = q; else pre->next = q; pre = p; p = p->next; } return head; }};
Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
注意： 前两个互换的时候，head 要改变位置。还要有一个 pre 指针。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */int getLength(ListNode *head) { int len = 0; while(head) { ++len; head = head->next; } return len;}class Solution {public: ListNode *rotateRight(ListNode *head, int k) { if(head == NULL) return NULL; k = k % getLength(head); if(k == 0) return head; ListNode *first, *second, *preFirst; first = second = head; for(int i = 1; i < k && second->next; ++i) // k-1 step second = second->next; //if(second->next == NULL) return head; while(second->next) { preFirst = first; first = first->next; second = second->next; } second->next = head; preFirst->next = NULL; return first; }};
Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note: Given n will always be valid. Try to do this in one pass.
思路： 双指针。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *removeNthFromEnd(ListNode *head, int n) { ListNode *pre = NULL, *p1, *p2; p1 = p2 = head; for(int i = 1; i < n; ++i) p2 = p2->next; while(p2->next) { pre = p1; p1 = p1->next; p2 = p2->next; } if(pre) pre->next = pre->next->next; return pre ? head : head->next; }};
63. Swap Nodes in Pairs && Rotate List && Remove Nth Node From End of List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。