反转链表/反转链表的某一段/左旋转链表/k长度反转/
反转字符串当中的单词/左旋转字符串
============================================
面试题16：反转链表
反转单链表，返回新链表的头指针。
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
ListNode *ReverseList(ListNode *pHead)
{ ListNode *pReversedHead = NULL; ListNode *cur = pHead; ListNode *prev = NULL; while(cur != NULL) { ListNode *pNext = cur->next; //最后一个节点，让新的头指针指向他 if(pNext == NULL) { pReversedHead = cur; } //头插法 cur->next = prev; //更新头 prev = cur; cur = pNext; } return pReversedHead; } |
Reverse Linked List II
反转链表的某一段[m, n]。1 ≤ m ≤ n ≤ length of list
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/**
* Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { /*dummy结点为了统一prev操作*/ ListNode dummy(-1); dummy.next = head; ListNode *prev = &dummy; for(int i = 0; i < m - 1; ++i) { prev = prev->next; } ListNode *const subHead = prev; /*prev指向最终"m...n子字符串"的末尾结点*/ prev = subHead->next; /*subhead...prev&& cur...n*/ /* cur指向当前要头插的结点， * 注意保持prev->next和后面还未处理的结点的连通性 */ ListNode *cur = prev->next; for(int i = m; i < n; ++i) { //要保证这个末尾结点和m...n后面的结点不断开 prev->next = cur->next; /*头插法*/ cur->next = subHead->next; subHead->next = cur; cur = prev->next; } return dummy.next; } }; |
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.
先遍历一遍，得出链表长度 len，注意 k 可能大于 len，因此令 k% = len。将尾节点 next 指针
指向首节点，形成一个环，接着往后跑 len k 步，从这里断开，就是要求的结果了。
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/**
* Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if(head == NULL || k == 0) { return head; } /*到这里说明至少有一个结点*/ int len = 1; ListNode *p = head; while(p->next) { len++; p = p->next; } /*算出移动步数*/ k = len - k % len; p->next = head; for(int step = 0; step < k; step++) { p = p->next; } /*更新head*/ head = p->next; /*尾结点指针指向空*/ p->next = NULL; return head; } }; |
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/**
* Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(head == NULL || head->next == NULL || k < 2) { return head; } ListNode dummy(-1); dummy.next = head; for(ListNode *prev = &dummy, *end = head; end != NULL; end = prev->next) { /*移动一步表示两个结点的范围，移动三步表示三个结点的返回*/ for(int i = 1; i < k && end != NULL; i++) { end = end->next; } /*如果end为空说明不满足k个了直接break不做reverse啦*/ if(end == NULL) { break; } /*用返回值更新prev，然后在用prev更新end*/ prev = reverse(prev, prev->next, end); } return dummy.next; } ListNode *reverse(ListNode *prev, ListNode *begin, ListNode *end) { /*保存[begin, end]后面连接的指针*/ ListNode *end_next = end->next; /*p指向的是头插法当前的头*/ ListNode *p = begin; /*cur指向当前要处理的节点*/ ListNode *cur = p->next; /*pNext指向下一次迭代要处理的节点*/ ListNode *pNext = cur->next; while(cur != end_next) { cur->next = p; p = cur; cur = pNext; pNext = (pNext ? pNext->next : NULL); } begin->next = end_next; prev->next = end; return begin; } }; |
Reverse Words in a String
反转字符串当中的单词，
前导和后导空格都去掉，中间多余的空格保留一个，可以认为任何非空的字符构成一个单词。
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
class Solution
{ public: /*翻转*/ void reverse(char *pBegin, char *pEnd) { while (pBegin < pEnd) { char tmp = *pBegin; *pBegin = *pEnd; *pEnd = tmp; pBegin ++; pEnd --; } } /*去除前导空格后导空格以及中间多余的空格*/ void removeDuplicates(string &s) { int index = 0; int num = s.length(); /*忽略前面和后面的空格*/ while (s[index] != ' ' && s[index] == ' ') { index ++; } int rIndex = num - 1; while (s[rIndex] == ' ') { s[rIndex] = ' '; rIndex --; } int cur = 0; /*去除中间多余的空格*/ while(index < num) { if(s[index] == ' ') { break; } if (s[index] == ' ') { /*保留中间的第一个空格*/ s[cur] = s[index]; cur++; /*忽略中间的其他空格*/ while (s[index] != ' ' && s[index] == ' ') { index ++; } } else { s[cur] = s[index]; cur++; index++; } } /*保证后面都是' '*/ while (cur < num) { s[cur] = ' '; cur++; } /*计算去除多余空格后字符串的长度*/ num = 0; while (s[num] != ' ') { num ++; } s.resize(num); return ; } void reverseWords(string &s) { if(s.length() == 0) { return ; } /*去除多余空格*/ removeDuplicates(s); char *pBegin = &s[0], *pEnd = &s[0]; while (*pEnd != ' ') { pEnd ++; } --pEnd; /*整体翻转*/ reverse(pBegin, pEnd); pBegin = pEnd = &s[0]; while (*pBegin != ' ') { if (*pBegin == ' ') { pBegin ++; pEnd ++; } else if (*pEnd == ' ' || *pEnd == ' ') { /*局部翻转*/ reverse(pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd++; } } } }; |
面试题042：翻转单词顺序VS左旋转字符串
题目一：
输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。
例如输入字符串“I am a student.”,则输出“student. a am I”。
思路一：
反转字符串的顺序，这样子每个单词的顺序也反转了，然后再次反转每个单词，这样子就做到了题目要求。
——关键是实现一个函数以反转字符串中的一段。
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream>
using namespace std; void Reverse(char *pBegin, char *pEnd) { if (pBegin == NULL || pEnd == NULL) { return ; } while(pBegin < pEnd) { char temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin ++; pEnd --; } } char *ReverseSentence(char *pData) { if(pData == NULL) return NULL; char *pBegin = pData; char *pEnd = pData; while(*pEnd != ' ') pEnd ++; pEnd--; // 翻转整个句子 Reverse(pBegin, pEnd); // 翻转句子中的每个单词 pBegin = pEnd = pData; while(*pBegin != ' ') { if(*pBegin == ' ') { pBegin ++; pEnd ++; } else if(*pEnd == ' ' || *pEnd == ' ') { Reverse(pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd ++; } } return pData; } int main() { char str[] = "I am a student."; ReverseSentence(str); printf("%s ", str); return 0; } |
题目二：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的末尾。请定义一个函数实现字符串左旋转操作的功能。
比如输入字符串“abcdefg”和数字2，该函数将返回左旋转2位得到的结果“cdefgab”。
思路一：
前两个字符ab为一部分，后面五个字符为一部分cdefg，然后两次反转，即可达到目的。
C++ Code
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream>
#include <string> using namespace std; void Reverse(char *pBegin, char *pEnd) { if (pBegin == NULL || pEnd == NULL) { return ; } while(pBegin < pEnd) { char temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin ++; pEnd --; } } char *LeftRotateString(char *pStr, int n) { if (pStr != NULL) { int nLength = static_cast<int>(strlen(pStr)); if (nLength > 0 && n > 0 && n < nLength) { char *pFirstStart = pStr; char *pFirstEnd = pStr + n - 1; char *pSecondStart = pStr + n; char *pSecondEnd = pStr + nLength - 1; Reverse(pFirstStart, pFirstEnd); Reverse(pSecondStart, pSecondEnd); Reverse(pFirstStart, pSecondEnd); } } return pStr; } int main() { char str[] = "abcdefg"; LeftRotateString(str, 2); printf("%s ", str); return 0; } |